답안 #13651

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13651 2015-02-27T05:18:36 Z baneling100 작은 사이클들 (YDX13_smallcycles) C++
0 / 1
0 ms 5096 KB
#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]) {
        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);
        }
    }
}

int component(int S) {

    int i, j, now, cnt=0;

    Visit[S]=0;
    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]=0;
            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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5096 KB Output is correct
2 Correct 0 ms 5096 KB Output is correct
3 Correct 0 ms 5096 KB Output is correct
4 Correct 0 ms 5096 KB Output is correct
5 Incorrect 0 ms 5096 KB Output isn't correct
6 Halted 0 ms 0 KB -