Cod sursa(job #1920115)

Utilizator blatulInstitutul de Arta Gastronomica blatul Data 9 martie 2017 22:30:53
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 100000, kMaxM = 200000;

int Edge[kMaxM];
vector<int> G[kMaxN];
int Dfn[kMaxN];

pair<int, int> Stk[kMaxN];

vector<int> Component[kMaxN];
int numComponents;

int Dfs(int node) {
    static int nextIdx = 0, stackSize = 0;
    int minPtr = Dfn[node] = ++nextIdx;
    
    for(const int& e : G[node]) {
        int son = node ^ Edge[e];
        
        if(Dfn[son] == 0) {
            Stk[stackSize++] = {node, son};
            
            int sonMinPtr = Dfs(son);
            minPtr = min(minPtr, sonMinPtr);
            
            if(Dfn[node] <= sonMinPtr) {
                int x, y;
                do {
                    x = Stk[stackSize - 1].first;
                    y = Stk[stackSize - 1].second;
                    
                    Component[numComponents].emplace_back(x);
                    Component[numComponents].emplace_back(y);
                    stackSize--;
                } while (x != node || y != son);
                numComponents++;
            }
        } else 
            minPtr = min(minPtr, Dfn[son]);
        
    }
    return minPtr;
}
 
int main() {
    #ifdef INFOARENA
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");
    #endif
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    int n, m;
    cin >> n >> m;
    
    for(int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        
        G[x].push_back(i);
        G[y].push_back(i);
        Edge[i] = x ^ y;
    }
    
    for(int i = 0; i < n; ++i)
        if(!Dfn[i])
            Dfs(i);
            
    cout << numComponents << '\n';
    for(int i = 0; i < numComponents; ++i) {
        sort(begin(Component[i]), end(Component[i]));
        Component[i].erase(unique(begin(Component[i]), end(Component[i])), end(Component[i]));
        
        for(const int& x : Component[i])
            cout << x + 1 << ' ';
        cout << '\n';
    }
}