Submission #3843

# Submission time Handle Problem Language Result Execution time Memory
3843 2013-08-31T08:46:13 Z waps12b Cactus? Not cactus? (kriii1_C) C++
0 / 1
4 ms 4192 KB
#include<cstdio>
#include<vector>
#include<memory.h>
using namespace std;

#define MAX_NODE 100001

struct Edge{
	int to; int rev;
	Edge(){}
	Edge(int a, int b) {to=a, rev=b;}
};
int dfn[MAX_NODE], nextdfn;
vector<Edge> g[MAX_NODE];

bool visited[MAX_NODE];

int dfs(int u, int p) {
	int i, minback;
	dfn[u] = nextdfn++;
	minback = nextdfn;
	for(int i = 0 ; i < g[u].size() ;i++) {
		int v = g[u][i].to, rev = g[u][i].rev;
		if( v == p ) continue;

		if( dfn[v] == -1 ) {
			int back = dfs(v,u);
			if( back > dfn[u] ) {
				g[u].erase(g[u].begin()+i);
				g[v].erase(g[v].begin()+rev);
				i--;
			}
			minback = min(minback, back);
		}
		else minback= min(minback, dfn[v]);
	}
	return minback;
}
int verNum = 0, chk = 1;
void dfs2(int u) {
	visited[u] = 1;
	verNum++;
	if(g[u].size() !=  2) chk = 0;
	for(int i = 0 ; i < g[u].size() ; i++) {
		int v = g[u][i].to;

		if(!visited[v]) dfs2(v);
	}
}
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	memset(dfn, -1, sizeof(dfn));
	for(int i = 0 ; i < m ; i++) {
		int st, end;
		scanf("%d%d", &st, &end);
		g[st].push_back(Edge(end, g[end].size()));
		g[end].push_back(Edge(st, g[st].size()-1));
	}
	for(int i = 1 ; i <= n ; i++) {
		if( dfn[i] == -1 ) dfs(i,-1);
	}
	for(int i = 1 ; i <= n ; i++) {
		if( !visited[i] ) {
			verNum = 0;
			chk = 1;
			dfs2(i);

			if( verNum == 1 ){
				chk = 1;
				continue;
			}
			if( !chk ) break;
		}
	}
	if(chk) printf("Cactus\n");
	else printf("Not cactus\n");
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 4040 KB Output is correct
2 Correct 0 ms 4040 KB Output is correct
3 Correct 4 ms 4192 KB Output is correct
4 Correct 0 ms 4064 KB Output is correct
5 Correct 0 ms 4040 KB Output is correct
6 Correct 4 ms 4172 KB Output is correct
7 Correct 0 ms 4172 KB Output is correct
8 Incorrect 0 ms 4172 KB Output isn't correct
9 Halted 0 ms 0 KB -