| ||||||||||
| 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