Submission #3787

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

C

#include <cstdio>
#include <vector>

using namespace std;

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

void dfs(int u){
	if( ch[u] ){
		cycle ++;
		return ;
	}
	ch[u] = 1;

	int si = v[u].size();

	for(int i=0; i<si; i++){
		if( !che[v[u][i].second] ){
			che[v[u][i].second] = 1;
			
			dfs( v[u][i].first );
			
		}
	}
	
}

int main(){
	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 );

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

 
}

• Subtask 1: 0 / 1