#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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
Correct |
0 ms |
5096 KB |
Output is correct |
| 6 |
Correct |
0 ms |
5228 KB |
Output is correct |
| 7 |
Correct |
0 ms |
5096 KB |
Output is correct |
| 8 |
Correct |
58 ms |
8792 KB |
Output is correct |
| 9 |
Correct |
36 ms |
8792 KB |
Output is correct |
| 10 |
Correct |
37 ms |
7208 KB |
Output is correct |
| 11 |
Correct |
57 ms |
8528 KB |
Output is correct |
| 12 |
Correct |
70 ms |
8792 KB |
Output is correct |
| 13 |
Correct |
0 ms |
5096 KB |
Output is correct |
| 14 |
Correct |
0 ms |
5096 KB |
Output is correct |
| 15 |
Correct |
0 ms |
5096 KB |
Output is correct |
| 16 |
Correct |
0 ms |
5096 KB |
Output is correct |
| 17 |
Correct |
49 ms |
9292 KB |
Output is correct |
| 18 |
Correct |
51 ms |
9556 KB |
Output is correct |
| 19 |
Correct |
44 ms |
9556 KB |
Output is correct |
| 20 |
Correct |
18 ms |
7328 KB |
Output is correct |
| 21 |
Correct |
31 ms |
9292 KB |
Output is correct |
| 22 |
Correct |
37 ms |
9556 KB |
Output is correct |
| 23 |
Correct |
0 ms |
5096 KB |
Output is correct |
| 24 |
Correct |
0 ms |
5096 KB |
Output is correct |
| 25 |
Correct |
0 ms |
5096 KB |
Output is correct |
| 26 |
Correct |
2 ms |
5440 KB |
Output is correct |
| 27 |
Correct |
5 ms |
5476 KB |
Output is correct |
| 28 |
Correct |
58 ms |
12668 KB |
Output is correct |
| 29 |
Correct |
67 ms |
13176 KB |
Output is correct |
| 30 |
Correct |
52 ms |
8960 KB |
Output is correct |
| 31 |
Correct |
80 ms |
13872 KB |
Output is correct |
| 32 |
Correct |
47 ms |
14964 KB |
Output is correct |
| 33 |
Correct |
0 ms |
5096 KB |
Output is correct |
| 34 |
Correct |
0 ms |
5096 KB |
Output is correct |
| 35 |
Correct |
0 ms |
5096 KB |
Output is correct |
| 36 |
Correct |
0 ms |
5364 KB |
Output is correct |
| 37 |
Correct |
46 ms |
8588 KB |
Output is correct |
| 38 |
Correct |
46 ms |
9904 KB |
Output is correct |
| 39 |
Correct |
44 ms |
9764 KB |
Output is correct |
| 40 |
Correct |
25 ms |
7276 KB |
Output is correct |
| 41 |
Correct |
37 ms |
9124 KB |
Output is correct |
| 42 |
Correct |
41 ms |
9648 KB |
Output is correct |
| 43 |
Correct |
0 ms |
5096 KB |
Output is correct |
| 44 |
Correct |
0 ms |
5096 KB |
Output is correct |
| 45 |
Correct |
1 ms |
5096 KB |
Output is correct |
| 46 |
Correct |
0 ms |
5360 KB |
Output is correct |
| 47 |
Correct |
7 ms |
5724 KB |
Output is correct |
| 48 |
Correct |
47 ms |
9300 KB |
Output is correct |
| 49 |
Correct |
65 ms |
9648 KB |
Output is correct |
| 50 |
Correct |
37 ms |
7568 KB |
Output is correct |
| 51 |
Correct |
56 ms |
9640 KB |
Output is correct |
| 52 |
Correct |
61 ms |
9828 KB |
Output is correct |
