| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
WHY WA?????#include<iostream>
#include<stack>
/*
#include<vector>
*/
#include<memory.h>
#define MAXN 10000
using namespace std;
class edge{
public:
int y;
edge *next;
edge(int _y,edge *_next):y(_y),next(_next){}
} *hLink[MAXN+1];
/*
class SCC{
public:
bool isin[MAXN+1];
int indegree,outdegree;
SCC(bool _isin[]){
memcpy(isin,_isin,MAXN+1);
}
};
vector<SCC> vcs;
*/
stack<int> stk;
int SCCnum[MAXN+1],SCCmember[MAXN+1];
int odegree[MAXN+1];
int n,m,dfn[MAXN+1],L[MAXN+1],num,SCCCnt,_tot;
bool instk[MAXN+1];
void Tarjan(int u){
dfn[u]=L[u]=++num;
stk.push(u);
instk[u]=true;
for (edge *p=hLink[u];p;p=p->next)
if (!dfn[p->y]){
Tarjan(p->y);
L[u]=min(L[u],L[p->y]);
}
else if (instk[p->y]) L[u]=min(L[u],dfn[p->y]);
if (dfn[u]==L[u]){
int v;
do{
v=stk.top();
SCCnum[v]=SCCCnt;
stk.pop();
} while (u!=v);
++SCCCnt;
/*
bool t[MAXN+1];
memset(t,false,sizeof(t));
do{
int v=stk.top();
t[v]=true;
stk.pop();
} while (u!=v);
SCC s(t);
vcs.push_back(s);
*/
}
}
int main (void){
cin>>n>>m;
for (int i=1;i<=n;++i) hLink[i]=NULL;
for (int i=0;i<m;++i){
int a,b;
cin>>a>>b;
hLink[a]=new edge(b,hLink[a]);
}
for (int i=1;i<=n;++i)
if (!dfn[i]) Tarjan(i);
for (int i=1;i<=n;++i){
++SCCmember[SCCnum[i]];
for (edge *p=hLink[i];p;p=p->next)
if (SCCnum[p->y]!=SCCnum[i]) ++odegree[SCCnum[i]];
}
for (int i=0;i<SCCCnt;++i)
if (!odegree[i]) _tot+=SCCmember[i];
cout<<_tot<<endl;
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator