Cod sursa(job #2199799)

Utilizator RaduVFVintila Radu-Florian RaduVF Data 29 aprilie 2018 02:47:42
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <vector>
#include <stack>
#define MAXN 100010
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<int> g[MAXN];
vector<int> component[MAXN];
stack<pair<int,int> > Stack;
int depth[MAXN],low[MAXN],seen[MAXN];
int components;
void CreateComponent(int node1,int node2){
    components++;
    while(Stack.top().first!=node1&&Stack.top().second!=node2){
        component[components].push_back(Stack.top().second);
        Stack.pop();
    }
    component[components].push_back(node2);
    component[components].push_back(node1);
    Stack.pop();
}
void DFS(int node,int father){
    depth[node]=low[node]=depth[father]+1;
    seen[node]=1;
    for(int i=0;i<g[node].size();i++){
        if(!seen[g[node][i]]){
            Stack.push(make_pair(node,g[node][i]));
            DFS(g[node][i],node);
            if(low[g[node][i]]>=depth[node])
                CreateComponent(node,g[node][i]);
        }
        if(g[node][i]!=father)
            low[node]=min(low[node],low[g[node][i]]);
    }
}
int main(){
    int n,m,a,b;
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    DFS(1,0);
    fout<<components<<endl;
    for(int i=1;i<=components;i++){
        for(int j=component[i].size()-1;j>=0;j--)
            fout<<component[i][j]<<' ';
        fout<<endl;
    }
    return 0;
}