求强连通分量,用邻接表储存,然后缩点,统计出度的点.话说我很勇敢的使用了邻接矩阵..然后就mle了
orz的是求强连通分量我还只会kosajura..
#include <iostream>
#include <stdio.h>
using namespace std;
int n,m;
int t=0;
const int MAXN=10001;
const int MAXM=50001;
bool used[MAXN];
int p[MAXN];
int pos[MAXN];
int len;
int d[MAXN];
int b[MAXN],bb[MAXN];
int x_[MAXM],y_[MAXM];
struct node
{
int v;
int next;
}ts[MAXM],tss[MAXM];
void dfs(int x)
{
used[x]=true;
int p_=b[x];
while(p_>0)
{
int i=ts[p_].v;
if (used[i]) {p_=ts[p_].next;continue;}
dfs(i);
p_=ts[p_].next;
}
t++;
p[t]=x;
}
void dfs1(int x)
{
used[x]=true;
int p=bb[x];
while(p>0)
{
int i=tss[p].v;
if (used[i]) {p=tss[p].next;continue;}
dfs1(i);
p=tss[p].next;
}
pos[x]=len;
}
void insert(int x,int y,int i)
{
ts[i].v=y;
ts[i].next=b[x];
b[x]=i;
tss[i].v=x;
tss[i].next=bb[y];
bb[y]=i;
}
int main()
{
memset(b,0,sizeof(b));
memset(bb,0,sizeof(bb));
scanf("%d %d",&n,&m);
for (int i=1;i<=m;i++)
{
int x,y;
scanf("%d %d",&x,&y);
x_[i]=x;
y_[i]=y;
insert(x,y,i);
}
memset(used,false,sizeof(used));
for (int i=1;i<=n;i++)
{
if (!used[i])
{
dfs(i);
}
}
len=0;
memset(used,false,sizeof(used));
for (int i=t;i>=1;i--)
{
int k=p[i];
if (!used[k])
{
len++;
dfs1(k);
}
}
memset(d,0,sizeof(d));
for (int i=1;i<=m;i++)
{
int x=pos[x_[i]];
int y=pos[y_[i]];
if (x==y) continue;
d[x]++;
}
int result=0;
int max_=0;
int co=0;
for (int i=1;i<=len;i++)
{
if (d[i]==0) co++;
}
if (co!=1) cout<<0<<endl;
else
{
for (int i=1;i<=len;i++)
if (d[i]==0)
{
for (int j=1;j<=n;j++)
if (pos[j]==i) result++;
}
cout<<result<<endl;
}
system("pause");
return 0;
}