題目傳送門
題目大意:
題面說得很清楚了。
思考過程:
很容易可以發現,若想使節點數最多,在同一個強連通分量内的所有點一定是同時取的,是以我們可以先将這個圖縮點成為DAG,而最大半聯通子圖也就是這個圖中最長的一條鍊,在DAG上求拓撲序做DP即可。
具體做法:
1.tarjan求強連通分量,縮點
2.去重邊求拓撲序
3.DP
代碼:
#include <bits/stdc++.h>
using namespace std;
const int maxm=+,maxn=+;
struct stu
{
int to,next;
}road[maxm],newroad[maxm]; int first[maxn],newfirst[maxn],cnt=;
struct lily
{
int x,y;
}len[maxm];
int num,n,m,mod,ans,ans2;
int size[maxn],dfn[maxn],low[maxn],book[maxn],col[maxn];
int du[maxn],side[maxn],dp[maxn];
queue <int> q;
stack <int> s;
void addedge(int x,int y)
{
road[++cnt].to=y;
road[cnt].next=first[x];
first[x]=cnt;
}
void tarjan(int now)
{
dfn[now]=low[now]=++cnt;
s.push(now);book[now]=;
for(int i=first[now];i;i=road[i].next)
{
int to=road[i].to;
if(!dfn[to]) { tarjan(to);low[now]=min(low[now],low[to]); }
else if(book[to]) low[now]=min(low[now],dfn[to]);
}
if(low[now]==dfn[now])
{
num++;
while(s.top()!=now)
{
size[num]++;
col[s.top()]=num;
book[s.top()]=;
s.pop();
}
size[num]++;col[s.top()]=num;book[s.top()]=;s.pop();
}
}
bool cmp(lily t1,lily t2)
{
return t1.x==t2.x?t1.y<t2.y:t1.x<t2.x;
}
void add_newedge(int x,int y)
{
newroad[++cnt].to=y;
newroad[cnt].next=newfirst[x];
newfirst[x]=cnt;
}
int main()
{
scanf("%d%d%d",&n,&m,&mod);
for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
len[i].x=x;len[i].y=y;
addedge(x,y);
}
cnt=;
for(int i=;i<=n;i++) if(!dfn[i]) tarjan(i);
// for(int i=1;i<=n;i++) printf("%d ",col[i]); printf("\n"); printf("%d\n",num);
for(int i=;i<=m;i++)
{
len[i].x=col[len[i].x];
len[i].y=col[len[i].y];
}
sort(len+,len++m,cmp);
int lastx,lasty;
cnt=;
for(int i=;i<=m;i++)
{
if(len[i].x!=len[i].y&&((len[i].x!=lastx)||(len[i].y!=lasty)))
{
add_newedge(len[i].x,len[i].y);
du[len[i].y]++;
}
lastx=len[i].x;lasty=len[i].y;
}
// for(int i=1;i<=num;i++) printf("%d ",size[i]); printf("\n");
for(int i=;i<=num;i++)
if(du[i]==) { q.push(i);side[i]=size[i];dp[i]=; }
// for(int i=1;i<=num;i++) printf("%d ",du[i]); printf("\n");
while(!q.empty())
{
int now=q.front();q.pop();
ans=max(side[now],ans);
for(int i=newfirst[now];i;i=newroad[i].next)
{
int to=newroad[i].to;
if(side[to]<side[now]+size[to])
{
side[to]=side[now]+size[to];
dp[to]=dp[now];
}
else if(side[to]==side[now]+size[to]) dp[to]=(dp[to]+dp[now])%mod;
du[to]--;
if(du[to]==) q.push(to);
}
}
printf("%d\n",ans);
for(int i=;i<=num;i++) if(side[i]==ans) ans2=(ans2+dp[i])%mod;
printf("%d\n",ans2);
return ;
}