Cod sursa(job #1386051)

Utilizator klamathixMihai Calancea klamathix Data 12 martie 2015 17:40:04
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include <bits/stdc++.h>
using namespace std;
#define VI vector<int>
#define PII pair<int, int>
const int MAXN = 1e5 + 5;
vector<int> G[MAXN];
vector<int> seen, lowPoint, depth;
vector<PII> st;
vector<VI> comps;

void dfs(int node, int f) {
    seen[node] = 1;
    lowPoint[node] = depth[node];

    for(auto tmp : G[node]) {
        if(tmp == f)
            continue;
        if(!seen[tmp]) {
            depth[tmp] = depth[node] + 1;
            st.push_back(make_pair(node, tmp));
            dfs(tmp, node);
            lowPoint[node] = min(lowPoint[tmp], lowPoint[node]);
            if(lowPoint[tmp] >= depth[node]) {
                unordered_set<int> newComp;
                bool doneLastOne = false;
                while(!st.empty() && !doneLastOne) {
                    newComp.insert(st.back().first);
                    newComp.insert(st.back().second);
                    if(st.back().first == node && st.back().second == tmp)
                        doneLastOne = true;
                    st.pop_back();
                }
                vector<int> newCompSol;
                for(auto tmp : newComp)
                    newCompSol.push_back(tmp);
                comps.push_back(newCompSol);
            }

        } else {
            lowPoint[node] = min(lowPoint[node], depth[tmp]);
        }
    }
}

int main() {
    
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");

    int n, m; cin >> n >> m;

    for(int i = 0; i < m; ++i) {
        int a, b; cin >> a >> b;
        --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    seen = vector<int> (n, 0);
    lowPoint = vector<int> (n, 0);
    depth = vector<int> (n, 0);

    for(int i = 0; i < n; ++i)
        if(!seen[i]) 
            dfs(i, -1);
        
    
    cout << comps.size() << "\n";

    for(auto comp: comps) {
        for(auto tmp : comp)
            cout << tmp + 1 << " ";
        cout << "\n";
    }
}