Submission #13687

#	Time	Username	Problem	Language	Result	Execution time	Memory
13687		baneling100	작은 사이클들 (YDX13_smallcycles)	C++98	1 / 1	80 ms	14964 KiB

E

#include <stdio.h>
#include <vector>
#include <queue>
#define V_MAX 100000
#define E_MAX 100000

using namespace std;

struct edge {
    int next;
    int num;
};
vector <edge> Edge[V_MAX+1];
queue <int> Q;
int V, E, Removed[E_MAX+1], Ans;
int Visit[V_MAX+1], Stack[V_MAX+1];

void findCycle(int now, int lev) {

    int i, j=Edge[now].size();

    Visit[now]=1;
    for(i=0 ; i<j ; i++) if(Edge[now][i].num!=Stack[lev-1] && !Removed[Edge[now][i].num]) {
        if(Visit[Edge[now][i].next]) Removed[Edge[now][i].num]=Removed[Stack[lev-1]]=Removed[Stack[lev-2]]=1;
        else {
            Stack[lev]=Edge[now][i].num;
            findCycle(Edge[now][i].next,lev+1);
        }
    }
    Visit[now]=0;
}

int component(int S) {

    int i, j, now, cnt=0;

    Visit[S]=1;
    Q.push(S);
    while(!Q.empty()) {
        now=Q.front();
        Q.pop();
        cnt++;
        j=Edge[now].size();
        for(i=0 ; i<j ; i++) if(!Removed[Edge[now][i].num] && !Visit[Edge[now][i].next]) {
            Visit[Edge[now][i].next]=1;
            Q.push(Edge[now][i].next);
        }
    }
    return  cnt;
}

int main(void) {

    int i, a, b;

    scanf("%d %d",&V,&E);
    for(i=1 ; i<=E ; i++) {
        scanf("%d %d",&a,&b);
        Edge[a].push_back({b,i});
        Edge[b].push_back({a,i});
    }
    findCycle(1,1);
    for(i=1 ; i<=V ; i++) if(!Visit[i]) {
        a=component(i);
        Ans+=(a-1)/2;
    }
    printf("%d",Ans);
    return 0;
}

• Subtask 1: 1 / 1