3 solutions

  • 3
    @ 2025-7-4 15:18:50
    #include <iostream>
    #include <vector>
    #include <stack>
    using namespace std;
    
    const int N = 2e4 + 5;
    int dfn[N], low[N]; // 时间戳,追溯值
    vector<int> g[N]; // 存图
    vector<int> vbcc[N]; // 点双连通分量
    int belong[N]; // 记录某点属于哪个SCC
    stack<int> stk; // Tarjan用到的临时栈
    int n, m, t, numVbcc;
    bool ap[N]; // 割点标记数组
    int apcnt;
    int root; // 特殊处理根节点是割点的情况
    
    void tarjan(int x) {
    	dfn[x] = low[x] = ++t;
    	stk.push(x);
    	// 根据定义,孤立点也是一个点双,但一定不是割点!!!
    	if (x == root && g[x].size() == 0) {
    		vbcc[++numVbcc].push_back(x);
    		return;
    	}
    
    	// 记录搜索树内满足割点判定条件的子节点的数量
    	int son = 0;
    	for (auto y : g[x]) {
    		// 非树边都可以用。重边和父节点都不用处理
    		if (dfn[y]) {
    			low[x] = min(low[x], dfn[y]);
    			continue;
    		}
    
    //		if (!dfn[y]) // (x,y)是树边
    		son++;
    		tarjan(y);
    		low[x] = min(low[x], low[y]);
    		// 满足点双判定法则
    		if (low[y] >= dfn[x]) {
    			// 只有非根 || 是根且子节点个数>=2才是割点
    			if (x != root || son >= 2) {
    				// 计算割点时一定要注意!!!可能会重复计算割点!!!
    				// 如果用标记数组,那么就要这样统计个数。
    				// 如果用vector,那么一定要记得排序去重!!!
    				apcnt += !ap[x];
    				ap[x] = 1;
    			}
    			// 点双处理,别忘了x本身,它可能属于多个点双
    			vbcc[++numVbcc].push_back(x);
    			int z;
    			do { // 不管是不是割点,一定形成了一个包含x的点双
    				z = stk.top();
    				stk.pop();
    				vbcc[numVbcc].push_back(z);
    			} while (y != z); // 要保证x不被弹出(允许x属于多个点双)
    		}
    	}
    }
    
    int main() {
    	cin >> n >> m;
    	int u, v;
    	for (int i = 1; i <= m; i++) {
    		cin >> u >> v;
    		g[u].push_back(v);
    		g[v].push_back(u);
    	}
    
    	// 大部分用Tarjan算法的题都要这样写!一定要注意!!!
    	for (int i = 1; i <= n; i++)
    		if (!dfn[i]) root = i, tarjan(i);
    
    	cout << apcnt << '\n';
    	for (int i = 1; i <= n; i++) if (ap[i]) cout << i << ' ';
    
    	return 0;
    }
    
    • 2
      @ 2025-7-4 19:21:52

      我发个只求割点的

      #include <bits/stdc++.h>
      using namespace std;
      typedef long long ll;
      const int N = 2e4 + 5,M = 1e5 + 5;
      int n,m,dfn[N],low[N],tot,sum;
      vector<int> g[N];
      bool ans[N];
      void tarjan(int u,int fa){
      	dfn[u] = ++tot;low[u] = tot;
      	bool flag = 0;
      	int cnt = 0;
      	for (int v : g[u]){
      		if (!dfn[v]){
      			tarjan(v,u),low[u] = min(low[u],low[v]);
      			if (low[v] >= dfn[u])	cnt++;	// 防重复算
      		}
      		else if (v != fa || flag)	low[u] = min(low[u],dfn[v]);
      		else	flag = 1;
      	}
      	if (cnt && fa || cnt > 1 && !fa)	ans[u] = 1;
      }
      int main(int argc, char **argv){
      	cin >> n >> m;
      	for (int i = 1;i <= m;i++){
      		int u,v;
      		cin >> u >> v;
      		if (u == v)	continue;
      		g[u].push_back(v);
      		g[v].push_back(u);
      	}
      	for (int i = 1;i <= n;i++){
      		if (!dfn[i])	tarjan(i,0);
      	}
      	for (int i = 1;i <= n;i++){
      		if (ans[i])	sum++;
      	}
      	cout << sum << '\n';
      	for (int i = 1;i <= n;i++){
      		if (ans[i])	cout << i << ' ';
      	}
      	return 0;
      }
      
      • -2
        @ 2025-7-4 15:41:02
        // 别说, 我的马蜂跟 @zengfj 还有几分相似
        
        #include <cstdio>
        #include <algorithm>
        #include <vector>
        #include <stack>
        #define N 20005
        
        using namespace std;
        
        int dfn[N], low[N], n, m, x, y, t = 0, apcnt = 0;
        // dfn 时间戳
        // low 追溯值
        // t 时间戳计数
        // apcnt 割点个数
        vector<int> g[N], aps;
        // g 存图
        // aps 存割点
        vector<vector<int> > vbccs; // 点双
        bool is_ap[N];  // 是否为割点
        stack<int> s;   // 栈
        
        // 模板, 自己看 PPT
        void tarjan(int x, int root) {
            dfn[x] = low[x] = ++t;
            s.push(x);
        
            // 是根并且没有边
            if (x == root && !g[x].size()) {
                vbccs.push_back(vector<int>(1, x));
                return;
            }
        
            int son = 0;
            for (const auto& y : g[x]) {
                // 非树边都可以用。重边和父节点都不用处理
                if (dfn[y]) {
                    low[x] = min(low[x], dfn[y]);
                    continue;
                }
        
                son++;
                tarjan(y, root);
                low[x] = min(low[x], low[y]);
        
                if (low[y] >= dfn[x]) {
                    // 非根 or 子节点个数大于 1
                    if (x != root || son > 1) {
                        // 记得去重, 我直接打标记
                        apcnt += !is_ap[x];
                        is_ap[x] = true;
                    }
        
                    // 记录答案
                    vbccs.push_back(vector<int>(1, x));
        
                    int z;
                    do {
                        z = s.top();
                        s.pop();
                        vbccs.back().push_back(z);
                    } while (y != z);   // x 不要出栈
                }
            }
        }
        
        int main() {
            scanf("%d%d", &n, &m);
        
            while (m--) {
                scanf("%d%d", &x, &y);
                g[x].push_back(y);
                g[y].push_back(x);
            }
        
            for (int i = 1; i <= n; i++)
                if (!dfn[i]) tarjan(i, i);
        
            for (int i = 1; i <= n; i++)
                if (is_ap[i]) aps.push_back(i);
        
            sort(aps.begin(), aps.end());
        
            printf("%d\n", (int)aps.size());
            for (const auto& i : aps)
                printf("%d ", i);
        
            return 0;
        }
        
        • 1

        Information

        ID
        416
        Time
        1000ms
        Memory
        125MiB
        Difficulty
        7
        Tags
        # Submissions
        61
        Accepted
        14
        Uploaded By