Submission #3390

#	Time	Username	Problem	Language	Result	Execution time	Memory
3390		solveit	Cactus? Not cactus? (kriii1_C)	C++98	0 / 1	76 ms	11828 KiB

C

#include <iostream>
#include <string>
#include <math.h>
#include <sstream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

int N, M, visited[100005], cnt[100005];
vector<int> G[100005];

void dfs(int u, int p) {
    visited[u] = 1;
    for(int i = 0;i<G[u].size();i++) {
        int v = G[u][i];
        if(visited[v] && v != p)
            cnt[v]++;
        if(visited[v]) continue;
        dfs(v, u);
    }
}

int main() {
    scanf("%d %d",&N, &M);
    for(int i = 0;i<M;i++) {
        int u, v;
        scanf("%d %d",&u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, -1);
    int ok = 1;
    for(int i = 1;i<=N;i++) {
        if(cnt[i] > 1)
            ok = 0;
    }
    if(ok)
        printf("Cactus\n");
    else
        printf("Not cactus\n");
    return 0;
}

• Subtask 1: 0 / 1