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