Cod sursa(job #1968006)

Utilizator eden001Muntean Natan eden001 Data 17 aprilie 2017 13:37:40
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
struct graf{
    int nod;
    graf*urm;
}*a[100001];
int n,m,i,index=1,ind[100001],ll[100001];
vector<int>con;
stack<int>s;
vector<vector<int>>C;
bool st[100001];
void add(int x,int y){
    graf*f=new graf;
    f->nod=y;
    f->urm=a[x];
    a[x]=f;
}
void scn(int k){
    ind[k]=index;
    ll[k]=index;
    index++;
    s.push(k);
    st[k]=true;
    graf*f=a[k];
    while(f){
        if(ind[f->nod]==0){
            scn(f->nod);
            ll[k]=min(ll[k],ll[f->nod]);}
        else if(st[f->nod])
            ll[k]=min(ll[k],ind[f->nod]);
        f=f->urm;
    }
    if(ll[k]==ind[k]){
        con.clear();
        int w=0;
        while(w!=k){
            w=s.top();
            con.push_back(w);
            s.pop();
            st[w]=false;
        }
        C.push_back(con);
    }
}

int main(){
    int x,y;
    fin>>n>>m;

    for(i=1;i<=m;i++){
        fin>>x>>y;
        add(x,y);
    }
    for(i=1;i<=n;i++)st[i]=false;
    for(i=1;i<=n;i++){
        if(ind[i]==0)scn(i);
    }
    x=C.size();
    fout<<x<<endl;
    for(i=0;i<x;i++){
        y=C[i].size();
        for(int j=0;j<y;j++)
            fout<<C[i][j]<<' ';
        fout<<endl;
    }

    return 0;
}