之前一直用的是tarjan第一次学习到这个来试一下。
唔，就是裸的算法，然后如果出度为0的点只有一个，输出这个点的大小。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<stack> #define mm 200004 #define mn 10020 using namespace std; stack<int>s; queue<int>q; struct ding{ int to,next,sum; }edge[mm],edge2[mm]; struct ding2{ int xx,yy; }a[mm]; int vis[mn],now[mn],ans,head[mn],head2[mn],node[mn],size[mn],num; int ru[mn],n,m,vv; bool cmp(ding2 k1,ding2 k2) {return (node[k1.xx]==node[k2.xx]?node[k1.yy]<node[k2.yy]:node[k1.xx]<node[k2.xx]);} void dfs(int x) { if (vis[x]) return; vis[x]=true; for (int i=head[x];i;i=edge[i].next) dfs(edge[i].to); s.push(x); } void redfs(int x) { if (node[x]) return; node[x]=num; size[num]++; for (int i=head2[x];i;i=edge2[i].next) redfs(edge2[i].to); } void add(int u,int v,ding*g,int*f) { int p=++g[0].sum; g[p].to=v; g[p].next=f[u];f[u]=p; } int main() { //freopen("cow4.in","r",stdin); //freopen("cow4.out","w",stdout); scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { scanf("%d%d",&a[i].xx,&a[i].yy); add(a[i].xx,a[i].yy,edge,head);add(a[i].yy,a[i].xx,edge2,head2); } for (int i=1;i<=n;i++) if (!vis[i])dfs(i); while (!s.empty()) { if (!node[s.top()]) {num++; redfs(s.top());} s.pop(); } for (int i=1;i<=m;i++) if (node[a[i].xx]>node[a[i].yy]) { int t=a[i].xx; a[i].xx=a[i].yy; a[i].yy=t; } sort(a+1,a+1+m,cmp); int t1=0,t2=0; for (int i=1;i<=m;i++) { if ((node[a[i].xx]==t1)&&(node[a[i].yy]==t2) ||(node[a[i].xx]==node[a[i].yy])) continue; t1=node[a[i].xx];t2=node[a[i].yy]; ru[t1]++; } for (int i=1;i<=num;i++) if (ru[i]==0) ans=size[i],vv++; if (vv==1) printf("%d ",ans); else printf("0 "); return 0; }