Cod sursa(job #2055554)

Utilizator DawlauAndrei Blahovici Dawlau Data 3 noiembrie 2017 13:52:58
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include<fstream>
#include<list>
#include<stack>
#include<bitset>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX=100005;
list<int>g[NMAX],scc[NMAX];
stack<int>s;
int scctime[NMAX],low_time[NMAX],n,m,k,node_time;
bitset<NMAX>in_stack;
void read_data(){
    int from,to;
    fin>>n>>m;
    while(m--){
        fin>>from>>to;
        g[from].push_back(to);
    }
}
void tarjan(int node){
    scctime[node]=low_time[node]=++node_time;
    s.push(node);
    in_stack[node]=true;
    list<int>::iterator it;
    for(it=g[node].begin();it!=g[node].end();++it)
        if(!scctime[*it]){
            tarjan(*it);
            low_time[node]=min(low_time[node],low_time[*it]);
        }
        else if(in_stack[*it])
            low_time[node]=min(low_time[node],low_time[*it]);
    if(scctime[node]==low_time[node]){
        ++k;
        int sccnode;
        do{
            sccnode=s.top();
            s.pop();
            scc[k].push_back(sccnode);
            in_stack[sccnode]=false;
        }while(node!=sccnode);
    }
}
void go_through_vertices(){
    int i;
    for(i=1;i<=n;++i)
        if(!scctime[i])
            tarjan(i);
}
void print(){
    fout<<k<<'\n';
    int i;
    list<int>::iterator it;
    for(i=1;i<=k;++i){
        for(it=scc[i].begin();it!=scc[i].end();++it)
            fout<<*it<<' ';
        fout<<'\n';
    }
}
int main(){
    read_data();
    go_through_vertices();
    print();
}