Cod sursa(job #1920950)

Utilizator iulian_f2kGuraliuc Iulian iulian_f2k Data 10 martie 2017 10:45:49
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
#include <climits>
#define NMAX 100005

using namespace std;

int N, M, nrComp;

vector<int> G[NMAX], inStack, comp[NMAX];
stack<int> S;
vector<bool> utilised;


int DFS(int node) {
    int pos = S.size() + 1, min1 = S.size() + 1, min2 = INT_MAX;
    S.push(node);
    utilised[node] = true;
    inStack[node] = S.size();
    for(int i = 0; i < G[node].size(); i++) {
        int neigh = G[node][i];
        if(!utilised[neigh]) {
            int dist = DFS(neigh);
            min1 = min(min1, dist);
            if(dist == pos) {
                nrComp++;
                while(1) {
                    comp[nrComp].push_back(S.top());
                    int TopBeforePop = S.top();
                    inStack[S.top()] = 0;
                    S.pop();
                    if(TopBeforePop == neigh)   break;
                }
                comp[nrComp].push_back(node);
            }
        }
        else if(inStack[neigh])     min2 = min(min2, inStack[neigh]);
    }
    return min(min1, min2);
}


int main() {
    freopen("biconex.in", "rt", stdin);
    freopen("biconex.out", "wt", stdout);
    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);
    }
    utilised.assign(N + 2, false);
    inStack.assign(N + 2, 0);

    DFS(1);

    cout << nrComp << '\n';
    for(int c = 1; c <= nrComp; c++) {
        for(int j = 0; j < comp[c].size(); j++)
            cout << comp[c][j] << ' ';
        cout << '\n';
    }
}