Submission #3878

#	Time	Username	Problem	Language	Result	Execution time	Memory
3878		Qwaz	Cactus? Not cactus? (kriii1_C)	C++98	1 / 1	68 ms	11856 KiB

C

#include <cstdio>
#include <vector>

struct edge {
	int to, num;
};

const int MAX=100020;

int n, m;
std::vector < edge > to[MAX];

void input(){
	scanf("%d%d", &n, &m);

	int i;
	for(i=0; i<m; i++){
		int f, s;

		scanf("%d%d", &f, &s);

		edge t;
		t.num = i;

		t.to = s;
		to[f].push_back(t);

		t.to = f;
		to[s].push_back(t);
	}
}

int parent[MAX], cycle[MAX], cFull=1, depth[MAX];
bool chk[MAX];

bool dfs(int now){
	int i;
	for(i=0; i<to[now].size(); i++){
		if(!chk[to[now][i].num]){
			chk[to[now][i].num] = 1;

			int next = to[now][i].to;
			if(parent[next] == 0){
				parent[next] = now;
				depth[next] = depth[now]+1;
				if(!dfs(next))
					return false;
			} else {
				int f = now, s = next;

				while(depth[f] > depth[s]){
					if(cycle[f] == 0)
						cycle[f] = cFull;
					else return false;
					f = parent[f];
				}
			
				while(depth[s] > depth[f]){
					if(cycle[s] == 0)
						cycle[s] = cFull;
					else return false;
					s = parent[s];
				}

				while(f != s){
					if(cycle[f] == 0)
						cycle[f] = cFull;
					else return false;

					if(cycle[s] == 0)
						cycle[s] = cFull;
					else return false;
				
					f = parent[f];
					s = parent[s];
				}

				if(cycle[f] == 0)
					cycle[f] = cFull;
				else return false;

				cFull++;
			}
		}
	}

	return true;
}

int main(){
	input();
	
	parent[1] = 1;
	puts(dfs(1)?"Cactus":"Not cactus");

	return 0;
}

• Subtask 1: 1 / 1