|
[mw_shl_code=c,true]#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100005
int head[maxn]={0}; int vis[maxn]={0}; int lowdex[maxn]={0};
int idx = 0; int book[maxn]={0};
struct edge {
int v, next;
} edges[2*maxn]; int tail;
int add_edge(int u, int v) {
edges[++tail].v=v;
edges[tail].next=head;
head=tail;
} int n, m; int cnt=0;
int dfs(int u, int fa) {
int ch = 0;
vis=++idx;
lowdex=idx;
for (int i = head; i; i=edges.next) {
if (!vis[edges.v]) {
ch++;
dfs(edges.v, u);
lowdex=std::min(lowdex, lowdex[edges.v]);
if (lowdex[edges.v]>=vis) {
if (book==0) cnt++;
book=1;
}
} else if (edges.v!=fa) {
lowdex=std::min(lowdex, vis[edges.v]);
}
}if (fa==-1&&ch==1) {
if (book==1) cnt--;
book=0;
}
}
int main() {
int a, b;
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i) {
scanf("%d %d", &a, &b);
add_edge(a, b);
add_edge(b, a);
} memset(vis, 0,sizeof(vis));
for (int i=1;i<=n;i++){
if (!vis) dfs(i,-1);
}printf("%d\n", cnt);
for(int i = 1; i <= n; ++i) {
if (book) printf("%d ", i);
}
return 0;
}
[/mw_shl_code]
链式前向星存图 |
|