Submission #3567

#	Time	Username	Problem	Language	Result	Execution time	Memory
3567		tncks0121	Cactus? Not cactus? (kriii1_C)	C++98	1 / 1	112 ms	13380 KiB

C

#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;

vector<int> G[100010],C[100010]; int Q[100010]; bool chk[100010];
int N,M;

void in(int x, int y)
{
	C[x].push_back(y);
	C[y].push_back(x);
}

int Depth[100010],Low[100010];
stack<pair<int, int> > S;

int main()
{
	int i,j,x,y;

	scanf ("%d %d",&N,&M);
	for (i=0;i<M;i++){
		scanf ("%d %d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}

	S.push(make_pair(1,-1)); Depth[1] = Low[1] = 1;
	while (!S.empty()){
		x = S.top().first; i = S.top().second; S.pop();

		if (i >= 0){
			if (Low[x] > Low[G[x][i]])
				Low[x] = Low[G[x][i]];
		}
		
		for (i++;i<G[x].size();i++){
			y = G[x][i];
			if (Depth[y] == 0){
				Depth[y] = Low[y] = Depth[x] + 1;
				S.push(make_pair(x,i));
				S.push(make_pair(y,-1));
				break;
			}
			else{
				if (Depth[y] + 1 < Depth[x]){
					in(x,y);
					if (Low[x] > Depth[y])
						Low[x] = Depth[y];
				}
			}
		}

		if (i == G[x].size() && !S.empty()){
			if (Low[x] <= Depth[S.top().first]){
				in(x,S.top().first);
			}
		}
	}

	for (i=1;i<=N;i++) if (!chk[i]){
		int head = -1, tail = -1;
		int V = 0, E = 0;

		Q[++head] = i; chk[i] = 1;
		while (tail < head){
			x = Q[++tail];
			V++; E += C[x].size();
			for (j=0;j<C[x].size();j++){
				y = C[x][j];
				if (!chk[y]){
					Q[++head] = y; chk[y] = 1;
				}
			}
		}

		if (V * 2 < E){puts("Not cactus"); return 0;}
	}
	puts("Cactus");

	return 0;
}

• Subtask 1: 1 / 1