Submission #3940

#	Time	Username	Problem	Language	Result	Execution time	Memory
3940		waps12b	Cactus? Not cactus? (kriii1_C)	C++98	1 / 1	80 ms	13828 KiB

C

#include<cstdio>
#include<vector>
#include<memory.h>
using namespace std;

#define MAX_NODE 100001

struct Edge{
	int to, can;
	Edge(int to) {this->to = to, can = 1;}
};
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;
		if( v == p ) continue;

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

		dfs2(v);
		num++;
	}
	if(num != 2) chk = 0;
}
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].push_back(Edge(st));
	}
	dfs(1,-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");
}

• Subtask 1: 1 / 1