Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

测试数据过了, discuss里的测试数据也过了,还是WA了,谁能帮忙看看那错了

Posted by lilei520007 at 2019-11-21 11:35:24 on Problem 1144
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator