Cod sursa(job #2059278)

Utilizator DawlauAndrei Blahovici Dawlau Data 6 noiembrie 2017 20:39:16
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include<fstream>
#include<list>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX=100005;
list<int>g[NMAX];
stack<pair<int,int> >s;
vector<int>bcc[NMAX];
int link[NMAX],lowlink[NMAX],n,m,node_time,nr_bcc;
void read_data(){
    int node1,node2;
    fin>>n>>m;
    while(m--){
        fin>>node1>>node2;
        g[node1].push_back(node2);
        g[node2].push_back(node1);
    }
}
void new_biconnected_component(int node1,int node2){
    int bnode1,bnode2;
    ++nr_bcc;
    do{
        bnode1=s.top().first;
        bnode2=s.top().second;
        s.pop();
        bcc[nr_bcc].push_back(bnode1);
        bcc[nr_bcc].push_back(bnode2);
    }while(bnode1!=node1 or bnode2!=node2);
}
void biconnected(int node){
    link[node]=lowlink[node]=++node_time;
    list<int>::iterator it;
    for(it=g[node].begin();it!=g[node].end();++it)
        if(!link[*it]){
            s.push(make_pair(node,*it));
            biconnected(*it);
            lowlink[node]=min(lowlink[node],lowlink[*it]);
            if(link[node]<=lowlink[*it])
                new_biconnected_component(node,*it);
        }
        else
            lowlink[node]=min(lowlink[node],link[*it]);
}
void print(){
    vector<int>::iterator it;
    int i;
    fout<<nr_bcc<<'\n';
    for(i=1;i<=nr_bcc;++i){
        sort(bcc[i].begin(),bcc[i].end());
        bcc[i].erase(unique(bcc[i].begin(),bcc[i].end()),bcc[i].end());
        for(it=bcc[i].begin();it!=bcc[i].end();++it)
            fout<<*it<<' ';
        fout<<'\n';
    }
}
int main(){
    read_data();
    biconnected(1);
    print();
}