代码略长,我的思路全注释好了,请各位大佬帮我查错。
#include<cctype>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10001;
int queue[N],head[N],rehead[N],dfn[N],low[N],stack[N],ori[N],out[N],num[N];
//queue用来存储连通分量的“根”如样例1中queue[1] = 3,queue[2] = 1;
//ori用来缩点,如ori[x] = y,表示点x可以合并在连通分量y中;out表示出度,num用来表示连通分量中点的个数
bool vis[N];
int idx,idy,top,tim,n,m,cnt;//tim时间戳,cnt连通分量计数器
struct cow
{
int u,v,next;
}edge[N * 5],ed[N * 5];
int rd()
{
int s = 0 , f = 1;
char ch = getchar();
while(!isdigit(ch))
{
if(ch == '-')
f = - 1;
ch = getchar();
}
while(isdigit(ch))
{
s = (s << 1) + (s << 3) + (ch ^ 48);
ch = getchar();
}
return f * s;
}
void write(int x)
{
if(x < 0)
{
putchar('-');
x = - x;
}
if(x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
void add(int u,int v)
{
edge[++idx].u = u;
edge[idx].v = v;
edge[idx].next = head[u];
head[u] = idx;
}
void readd(int u,int v)
{
ed[++idy].u = u;
ed[idy].v = v;
ed[idy].next = rehead[u];
rehead[u] = idy;
}
void tarjan(int x)
{
dfn[x] = low[x] = ++tim;
stack[++ top] = x;
vis[x] = 1;
for(int i = head[x] ; i ; i = edge[i].next)
{
int y = edge[i].v;
if(!dfn[y])
{
tarjan(y);
low[x] = min(low[x],low[y]);
}
else if(dfn[y] && vis[y])
{
low[x] = min(low[x],low[y]);
}
}
if(dfn[x] == low[x])
{
int y;
cnt ++;
while(y = stack[top --])
{
queue[cnt] = x;//将连通量的“根”x记录下来
ori[y] = x;//y可以合并在为连通分量x中
vis[y] = 0;//出栈
num[x] ++;//连通分量x中的点的数量+1
if(x == y)//到“根”时退出
break;
}
}
}
int main()
{
n = rd(),m = rd();
for(int i = 1 ; i <= m; i ++)
{
int u = rd(),v = rd();
add(u,v);
}
for(int i = 1 ; i <= n ; i ++)
if(!dfn[i])
tarjan(i);
for(int i = 1 ; i <= n ; i ++)//重新建图
{
int eu = ori[edge[i].u],ev = ori[edge[i].v];
if(eu != ev)
{
readd(eu,ev);
}
}
for(int i = 1 ; i <= idy ; i ++)//枚举每一条边
{
int u = ed[i].u,v = ed[i].v;//取此边的初、始点;
out[u]++;//记录出度
}
int ans;
bool flag;
for(int i = 1 ; i <= cnt ; i ++)//枚举每一个连通分量
{
int j = queue[i];//取连通分量的“根”
if(!out[j])//没有出度
{
if(!flag)//是第一个没有出度
{
ans = j;//记录答案分量
flag = 1;//标记答案已饱和
}
else//答案过量,不符题意
{
return printf("0"),0;
}
}
}
write(num[ans]);//输出分量中的点数
}
再次感谢各位大佬!!