Submission #5713

#	Time	Username	Problem	Language	Result	Execution time	Memory
5713		baneling100	Cactus? Not cactus? (kriii1_C)	C++98	1 / 1	60 ms	11760 KiB

C

#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;

vector <int> A[100001];
int N, M, S[100001], top, check[100001], cycle[100001];

void input(void)
{
    int i, x, y;

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

void process(int now, int prev)
{
    int i, j, k;

    j=A[now].size();
    for(i=0 ; i<j ; i++)
        if(A[now][i]!=prev)
        {
            if(check[A[now][i]])
                for(k=check[A[now][i]] ; k<=top ; k++)
                {
                    if(cycle[S[k]])
                    {
                        printf("Not cactus");
                        exit(0);
                    }
                    else
                        cycle[S[k]]=1;
                }
            else
            {
                S[++top]=A[now][i];
                check[A[now][i]]=top;
                process(A[now][i],now);
                top--;
            }
        }
}

int main(void)
{
    input();
    S[++top]=1;
    check[1]=top;
    process(1,0);
    top--;
    printf("Cactus");

    return 0;
}

• Subtask 1: 1 / 1