题意：n个节点m条边的图，删除某个节点及他相连的所有边之后，剩下的图就成了一棵树。找出所有这样的节点。
思路：上次去清华面试的B题，当时就是在瞎写。太菜了。
其实就是两点，一是删除一个点是树，那么剩下来只有$n-2$条边。也就是说删掉的那个点的度是$m - (n - 2)$
其次，删掉了这个点之后还需要保证图的连通性，也就是说割点一定不是。
所以就先用Tarjan求出所有割点，再找不是割点且度是$m - (n - 2)$的点。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<map> 4 #include<set> 5 #include<cstring> 6 #include<algorithm> 7 #include<vector> 8 #include<cmath> 9 #include<stack> 10 #include<queue> 11 #include<iostream> 12 13 #define inf 0x3f3f3f3f 14 using namespace std; 15 typedef long long LL; 16 typedef pair<int, int> pr; 17 18 int n, m; 19 const int maxn = 1e5 + 5; 20 struct edge{ 21 int to, nxt; 22 }e[maxn * 2]; 23 int tot = 1, head[maxn], dfn[maxn], low[maxn]; 24 25 void add(int x, int y) 26 { 27 e[++tot].to = y; 28 e[tot].nxt = head[x]; 29 head[x] = tot; 30 e[++tot].to = x; 31 e[tot].nxt = head[y]; 32 head[y] = tot; 33 } 34 35 int num, root; 36 bool cut[maxn]; 37 void tarjan(int x) 38 { 39 dfn[x] = low[x] = ++num; 40 int flag = 0; 41 for(int i = head[x]; i; i = e[i].nxt){ 42 int y = e[i].to; 43 if(!dfn[y]){ 44 tarjan(y); 45 low[x] = min(low[x], low[y]); 46 if(low[y] >= dfn[x]){ 47 flag++; 48 if(x != root || flag > 1)cut[x] = true; 49 } 50 } 51 else low[x] = min(low[x], dfn[y]); 52 } 53 } 54 55 int deg[maxn]; 56 int main() 57 { 58 scanf("%d%d", &n, &m); 59 for(int i = 0; i < m; i++){ 60 int x, y; 61 scanf("%d%d", &x, &y); 62 add(x, y); 63 deg[x]++;deg[y]++; 64 } 65 for(int i = 1; i <= n; i++){ 66 if(!dfn[i]){ 67 root = i; 68 tarjan(i); 69 } 70 } 71 vector<int>ans; 72 for(int i = 1; i <= n; i++){ 73 if(!cut[i] && deg[i] == m - (n - 2))ans.push_back(i); 74 } 75 printf("%d %d", ans.size(), ans[0]); 76 for(int i = 1; i < ans.size(); i++){ 77 printf(" %d", ans[i]); 78 } 79 printf(" "); 80 return 0; 81 }
---恢复内容结束---