Cod sursa(job #1970821)

Utilizator RaZxKiDDavid Razvan RaZxKiD Data 19 aprilie 2017 17:09:38
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream in("biconex.in");
ofstream out("biconex.out");

int n,m;
vector<int> L[100005];
stack<int> S;
vector<int> SOL[100005];
int comp;
int LOW[100005],DFN[100005];

void read(){
    in>>n>>m;
    for(int i=1,x,y;i<=m;i++){
        in>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
}
bool U[100005];
void dfs(int nod, int par){
    if(U[nod]==1)
        return;
    U[nod]=1;
    int c;
    S.push(nod);
    for(auto x : L[nod]){
        if(x==par)
            continue;
        if(!LOW[x]){
            c=S.size();
            LOW[x]=DFN[x]=DFN[nod]+1;

            dfs(x,nod);
            LOW[nod]=min(LOW[nod],LOW[x]);
            if(LOW[x]>=DFN[nod]){
                comp++;
                while(S.size()>c){
                    SOL[comp].push_back(S.top());
                    S.pop();
                }
                SOL[comp].push_back(nod);
            }
        }
        else LOW[nod]=min(LOW[nod],DFN[x]);
    }
}
void solve(){
    LOW[1]=DFN[1]=1;
    dfs(1,-1);
    out<<comp<<"\n";
    for(int i=1;i<=comp;i++){
        for(auto x : SOL[i])
            out<<x<<" ";
        out<<"\n";
    }
}
int main(){
    read();
    solve();
    return 0;
}