Submission #3843

#	Time	Username	Problem	Language	Result	Execution time	Memory
3843		waps12b	Cactus? Not cactus? (kriii1_C)	C++98	0 / 1	4 ms	4192 KiB

C

#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");
}

• Subtask 1: 0 / 1