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 |
Re:不知道为什么WA.和正确程序跑了100多组数据依然一致In Reply To:不知道为什么WA.和正确程序跑了100多组数据依然一致 Posted by:SunnyElemeNt at 2010-05-31 15:04:12 找到错了 k达成Cnt了 #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cstdlib> #include<cmath> #define maxn 10005 #define maxm 50005 using namespace std; int y[maxm],now[maxn],pre[maxm],tot,LOW[maxn],DFN[maxn],stack[maxn],Belong[maxn],k,Sum; int outdegree[maxn],step,Cnt,top,N,M; bool visit[maxn]; void addedge(int from , int to){ tot++; pre[tot] = now[from] ; now[from] = tot ; y[tot] = to; } void tarjan(int u){ DFN[u] = LOW[u] = ++step ; visit[u] = 1; stack[++top] = u ; for (int mark = now[u] ; mark > 0 ; mark = pre[mark]) { int v = y[mark]; if (!DFN[v]) { tarjan(v); LOW[u] = min(LOW[u],LOW[v]); } else { if (visit[v]) LOW[u] = min(LOW[u],DFN[v]); } } if (LOW[u] == DFN[u]) { Cnt++; int v; do { v = stack[top--]; Belong[v] = Cnt; visit[v] = false; } while (v!=u); } } void initialize(){ scanf("%d%d",&N,&M); tot = 0 ; for (int i = 1 ; i <= M ; i++) { int A , B; scanf("%d%d",&A,&B); addedge(A , B); } } void solve(){ memset(DFN,0,sizeof(DFN)); memset(visit,false,sizeof(visit)); step = top = Cnt = 0 ; for (int i = 1 ; i <= N ; i++) if (!DFN[i]) tarjan(i); memset(outdegree,0,sizeof(outdegree)); for (int i = 1 ; i <= N ; i++) { for (int mark = now[i] ; mark > 0 ; mark = pre[mark]) { int j = y[mark]; if (Belong[i]!=Belong[j]) outdegree[Belong[i]]++; } } Sum = 0 ; for (int i = 1 ; i <= Cnt ; i++) if (outdegree[i] == 0) { Sum++; k = i ; } } void outitialize(){ if (Sum != 1) { printf("%d\n",0); exit(0); } int Answer = 0 ; for (int i = 1 ; i <= N ; i++) if (Belong[i] == k) { Answer++; } printf("%d\n",Answer); } int main(){ int t ; t = 1; while (t--) { initialize(); solve(); outitialize(); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator