Submission #3909

#	Time	Username	Problem	Language	Result	Execution time	Memory
3909		BalloonCollector	Cactus? Not cactus? (kriii1_C)	C++98	1 / 1	72 ms	12152 KiB

C

#include <cstdio>
#include <vector>

using namespace std;

typedef pair <int, int> ii;
int ch[100002], p[100002], c[100002], che[100002];
vector <ii> v[100002];
int cycle = 0;

void dfs(int u){
	if( cycle ) return ;
	
	ch[u] = 1;
	int si = v[u].size();

//	printf("%d\n", u);

	for(int i=0; i<si; i++){
		if( !che[v[u][i].second] ){
			che[v[u][i].second] = 1;
			
			if( !ch[v[u][i].first] ){
				p[v[u][i].first] = u;
				dfs( v[u][i].first );
			}
			else if( p[u] != v[u][i].first ){
				int pos = u;
				c[v[u][i].first] ++;
				if( c[v[u][i].first] >= 2 ) {
					cycle = 1;
					return;
				}
				//printf("cycle %d \n", v[u][i]);
				while( pos != v[u][i].first){
					//printf("p %d \n", pos);
					c[pos]++;
					if( c[pos] >= 2 ){
						cycle = 1;
						//puts("");
						return;
					}
					pos = p[pos];
				}
				//puts("");
				
			}
		}
	}
	
}

int main(){  //freopen("input.txt", "r", stdin);
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i=0; i<m; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		v[x].push_back(ii(y, i));
		v[y].push_back(ii(x, i));
	}

	dfs( 1 );

	/*for(int i=1; i<=n; i++)
		printf("%d ", c[i]);
	puts("");*/

	if( !cycle ) printf("Cactus\n");
	else printf("Not cactus\n");
	

 
}

• Subtask 1: 1 / 1