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 |
测试数据过了, discuss里的测试数据也过了,还是WA了,谁能帮忙看看那错了#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn = 100+5; int low[maxn]; int dfn[maxn]; int head[maxn]; struct edge { int to; int next; }edge[maxn*maxn]; int cnt; int num; int root; bool iscut[maxn]; void add(int u, int v) { edge[++cnt].next = head[u]; edge[cnt].to = v; head[u] = cnt; } void init() { memset(low, 0x0, sizeof(low)); memset(dfn, 0x0, sizeof(dfn)); memset(head, 0x0, sizeof(head)); memset(iscut, false, sizeof(iscut)); cnt = 0; num = 0; } void tarjan(int u, int fa) { dfn[u] = low[u] = ++num; int v; int flag = 0; for (int i=head[u]; i; i=edge[i].next) { v = edge[i].to; if (v == fa) { continue; } if (!dfn[v]) { tarjan(v, u); low[u] = min(low[u], low[v]); if (low[v] >= dfn[u]) { if (u!=root || flag >1 ) { iscut[u] = true; } } } else { low[u] = min(low[u], dfn[v]); } } } int main() { int n, m; while (cin >> n && n) { int u, v; init(); while(cin >> u && u) { while (1) { char c = getchar(); if (c == '\n') break; cin >> v; add(u, v); add(v, u); } } for (int i=1; i<=n; i++) { if (!dfn[i]) { root = i; tarjan(i,0); } } int number = 0; for(int i=1; i<=n; i++) { if (iscut[i]) number++; } cout << number << 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