实际上是一道tarjan缩点的题，tarjan求点双联通分量，主要思路就是缩完点之后，找新图中的叶子节点的个数，然后带入公式就行了。详情见lba的博客。
题干：
。。。略。
代码：
#include<iostream> #include<cstdio> #include<cmath> #include<ctime> #include<queue> #include<algorithm> #include<cstring> using namespace std; #define duke(i,a,n) for(int i = a;i <= n;i++) #define lv(i,a,n) for(int i = a;i >= n;i--) #define clean(a) memset(a,0,sizeof(a)) const int INF = 1 << 30; typedef long long ll; typedef double db; template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } struct node { int l,r,nxt; }a[300010]; int lst[200010],len = 1,cnt = 0; void add(int x,int y) { a[++len].l = x; a[len].r = y; a[len].nxt = lst[x]; lst[x] = len; } int n,m,low[200010],dfn[200010]; int from[200010],col[200010]; int du[200010]; int vis[200010]; int top = 0,st[100010],tot = 0; void tarjan(int u,int g) { bool flag = 0; vis[u] = 1;st[++top] = u; low[u] = dfn[u] = ++cnt; for(int k = lst[u];k;k = a[k].nxt) { int y = a[k].r; if(y == g && !flag) { flag = 1; continue; } if(!dfn[y]) { tarjan(y,u); low[u] = min(low[u],low[y]); } else if(vis[y]) low[u] = min(low[u],dfn[y]); } if(low[u] == dfn[u]) { int p = 0; tot++; do { p = st[top--]; col[p] = tot; vis[p] = 0; } while(p != u); } } int main() { read(n);read(m); duke(i,1,m) { int x,y; read(x);read(y); add(x,y); add(y,x); } duke(i,1,n) if(!dfn[i]) tarjan(i,0); int ans = 0; duke(i,1,n) { for(int k = lst[i];k;k = a[k].nxt) { int x = a[k].l; int y = a[k].r; if(col[x] != col[y]) { du[col[x]]++; du[col[y]]++; } } } // for(int i = 1; i <= tot; ++i) printf("%d ", du[i]); puts("") duke(i,1,tot) if(du[i] == 2) ans++; if(tot == 1) printf("0 "); else printf("%d ",(ans + 1) / 2); return 0; }