tarjan缩点T了!求调1
#include<bits/stdc++.h>
using namespace std;
const int MX = 1000100;
int n,m,a,b;
int fst[MX],nxt[MX],vv[MX],uu[MX],in[MX],lnum;
int stk[MX],dfn[MX],colour[MX],low[MX],vis[MX],vi[MX],d[MX],inn[MX],inn1[MX],cont,top,cnm,dnm;
namespace IO{
const int SIZE=1<<21;
static char ibuf[SIZE],obuf[SIZE],*iS,*iT,*oS=obuf,*oT=oS+SIZE-1;
int qr;
char qu[55],c;
bool f;
#define getchar() (IO::iS==IO::iT?(IO::iT=(IO::iS=IO::ibuf)+fread(IO::ibuf,1,IO::SIZE,stdin),(IO::iS==IO::iT?EOF:*IO::iS++)):*IO::iS++)
#define putchar(x) *IO::oS++=x,IO::oS==IO::oT?flush():0
#define flush() fwrite(IO::obuf,1,IO::oS-IO::obuf,stdout),IO::oS=IO::obuf
#define puts(x) IO::Puts(x)
template<typename T>
inline void read(T&x){
for(f=1,c=getchar();c<48||c>57;c=getchar())f^=c=='-';
for(x=0;c<=57&&c>=48;c=getchar()) x=(x<<1)+(x<<3)+(c&15);
x=f?x:-x;
}
template<typename T>
inline void write(T x){
if(!x) putchar(48); if(x<0) putchar('-'),x=-x;
while(x) qu[++qr]=x%10^48,x/=10;
while(qr) putchar(qu[qr--]);
}
inline void Puts(const char*s){
for(int i=0;s[i];i++)
putchar(s[i]);
putchar('\n');
}
struct Flusher_{~Flusher_(){flush();}}io_flusher_;
}
using IO::read;
using IO::write;
void add(int u,int v){
lnum++;
vv[lnum] = v;
nxt[lnum] = fst[u];
fst[u] = lnum;
++in[v];
}
int find(){
int ans = 0;
for(register int i = 1;i <= a;++i){
for(register int j = fst[d[i]]; j;j = nxt[j]){
if(!vi[vv[j]]) ans++;
}
}
//cout << ans <<endl;
return ans;
}
void tarjan(int x)
{
low[x] = dfn[x] = ++dnm;
stk[++top] = x;
vis[x] = 1;
for(register int i = fst[x]; i;i = nxt[i])
{
int y = vv[i];
if(!dfn[y]){
tarjan(y);
low[x] = min(low[x],low[y]);
}else{
if(vis[y]){
low[x] = min(low[x],low[y]);
}
}
}
if(dfn[x] == low[x]){
//++cnm;
++cont;
a = 0;
while(x != stk[top]){
int y = stk[top--];
vis[y] = 0;
d[++a] = y;
vi[y] = 1;
inn1[cont]++;
}
int y = stk[top--];
vis[y] = 0;
d[++a] = y;
vi[y] = 1;
inn1[cont]++;
inn[cont] = find();
a = 0;
memset(vi,0,sizeof(vi));
}
}
int main(){
read(n),read(m);
for(register int i = 1;i <= m;i++)
{
read(a),read(b);
add(a,b);
}
for(register int i = 1;i <= n;++i)
{
if(!dfn[i]) tarjan(i);
}
int c = 0,ans;
for(register int i = 1;i <= cont;++i){
if(!inn[i]) c++,ans = i;
}
if(c == 1){
write(inn1[ans]);
}else{
putchar('0');
}
return 0;
}