Cod sursa(job #1968028)

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

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,index=1,ind[100001],ll[100001];
vector<int>con,a[100001];
stack<int>s;
vector<vector<int>>C;
bool st[100001];
void scn(int k){
    ind[k]=index;
    ll[k]=index;
    index++;
    s.push(k);
    st[k]=true;
    vector <int>::iterator it;
    for(it=a[k].begin();it!=a[k].end();it++){
        if(ind[*it]==0){
            scn(*it);
            ll[k]=min(ll[k],ll[*it]);}
        else if(st[*it])
            ll[k]=min(ll[k],ind[*it]);
    }
    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,i;
    fin>>n>>m;

    for(i=1;i<=m;i++){
        fin>>x>>y;
        a[x].push_back(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;
}