답안 #13651

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

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]) {
        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;
}

Subtask #1

0.0 / 1.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	-