2 条题解

  • 0
    @ 2024-10-31 19:46:44

    AC代码:

    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5 + 5;
    int n, m, dfn[maxn], low[maxn], idx, rt;
    bool cut[maxn];
    vector<int> g[maxn];
    
    void tarjan(int u, int p) {
    	dfn[u] = low[u] = ++idx;
    	int son_cnt = 0;
    	for (auto v : g[u]) {
    		if (v == p) continue;
    		if (!dfn[v]) {
    			tarjan(v, u);
    			son_cnt++;
    			low[u] = min(low[u], low[v]);
    			if (u != rt && low[v] >= dfn[u])
    				cut[u] = true;
    		}
    		else
    			low[u] = min(low[u], dfn[v]);
    	}
    	if (u == rt && son_cnt > 1)
    		cut[u] = true;
    }
    
    int main() {
    	scanf("%d%d", &n, &m);
    	while (m--) {
    		int u, v;
    		scanf("%d%d", &u, &v);
    		g[u].push_back(v);
    		g[v].push_back(u);
    	}
    	for (int i = 1; i <= n; i++)
    		if (!dfn[i])
    			rt = i,
    			tarjan(i, -1);
    	int cnt = 0;
    	for (int i = 1; i <= n; i++)
    		cnt += cut[i];
    	printf("%d\n", cnt);
    	for (int i = 1; i <= n; i++)
    		if (cut[i])
    			printf("%d ", i);
    	return 0;
    }
    
    
    
    
    • 0
      @ 2024-10-31 19:38:35

      代码有问题:

      #include <bits/stdc++.h>
      using namespace std;
      const int maxn = 1e5 + 5;
      int n, m, dfn[maxn], low[maxn], idx, rt;
      bool cut[maxn];
      vector<int> g[maxn];
      
      void tarjan(int u, int p) {
      	dfn[u] = low[u] = ++idx;
      	int son_cnt = 0;
      	for (auto v : g[u]) {
      		if (v == p) continue;
      		if (!dfn[v]) {
      			tarjan(v, u);
      			son_cnt++;
      			low[u] = min(low[u], low[v]);
      		}
      		else 
      			low[u] = min(low[u], dfn[v]);
      	}
      	if (dfn[u] == low[u]) {
      		if (u != rt && son_cnt > 0 || u == rt && son_cnt > 1)
      			cut[u] = true;
      	}
      }
      
      int main() {
      	scanf("%d%d", &n, &m);
      	while (m--) {
      		int u, v;
      		scanf("%d%d", &u, &v);
      		g[u].push_back(v);
      		g[v].push_back(u);
      	}
      	for (int i = 1; i <= n; i++)
      		if (!dfn[i])
      			rt = i,
      			tarjan(i, -1);
      	int cnt = 0;
      	for (int i = 1; i <= n; i++)
      		cnt += cut[i];
      	printf("%d\n", cnt);
      	for (int i = 1; i <= n; i++)
      		if (cut[i])
      			printf("%d ", i);
      	return 0;
      }
      
      
      
      
      • 1

      信息

      ID
      68
      时间
      1000ms
      内存
      256MiB
      难度
      10
      标签
      (无)
      递交数
      5
      已通过
      4
      上传者