Submission #3453

#	Time	Username	Problem	Language	Result	Execution time	Memory
3453		wookayin	Cactus? Not cactus? (kriii1_C)	C++98	1 / 1	64 ms	14120 KiB

C

#include <stdio.h>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n,e;
vector<int> graph[100000];
int t[100000];
int m[100000];
int tcnt;
 
//1 if ok
int dfs(int nod, int par)
{
    m[nod] = t[nod] = ++tcnt;
        int cnt = 0;
        for(int i = 0; i < graph[nod].size(); i++){
                int next = graph[nod][i];
                if (next == par) continue;
                if (t[next] != 0 && t[next] < t[nod]) {
                        // back edge
                        m[nod] = min(m[nod], t[next]);
                        cnt++;
                        if (cnt >= 2) 
                                return 0;
                } else  if (t[next] == 0) {
                        int res = dfs(next, nod);
                        m[nod] = min(m[nod], m[next]);
                        if (res == 0)
                                return 0;
                        if (t[nod] >= m[next]) {
                                cnt ++;
                                if (cnt >= 2)
                                        return 0;
                        }
                }
        }
        return 1;
}
 
int main()
{
        scanf("%d%d",&n,&e);
        for(int i = 0;i < e;i ++){
                int a,b;
                scanf("%d%d",&a,&b);
                a--,b--;
                graph[a].push_back(b);
                graph[b].push_back(a);
        }
        if (dfs(0, -1) == 0) {
                printf("Not cactus\n");
        } else {
                printf("Cactus\n");
        }
        return 0;
}

• Subtask 1: 1 / 1