Cod sursa(job #1022015)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 4 noiembrie 2013 16:46:36
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>

#define DN 100005
#define pb push_back
#define top stiva[0]
using namespace std;


vector<int> list[DN],tmp;
vector< vector<int> > rez;
bitset<DN> viz,ap;
int stiva[DN],low[DN],p,niv[DN];

void dfs(int nod)
{
    viz[nod]=true;
    low[nod]=++p;
    niv[nod]=p;
    stiva[++top]=nod;
    ap[ nod ] = true;


    for(int i=0;i<list[nod].size();++i){

        int next_nod=list[nod][i];
        if(!viz[next_nod]){

            dfs(next_nod);
            low[nod]=min(low[nod],low[next_nod]);
        }
        else
            if(ap[next_nod]==true)
                low[nod]=min(low[nod],low[next_nod]);
    }
    if(low[nod]==niv[nod])
    {
        while(1)
        {
            ap[ stiva[top] ] = false;
            int a=stiva[top];
            tmp.pb(stiva[top]);
            --top;
            if(a==nod)
                break;
        }


        rez.pb(tmp);
        tmp.clear();
    }
    //cout<<"NOD:"<<nod<<" LOW :"<<low[nod]<<endl;
}


int main()
{
    int n,m;

    ifstream f("ctc.in");
    ofstream g("ctc.out");
    f>>n>>m;
    for(;m;--m)
    {
        int a,b;
        f>>a>>b;
        list[a].pb(b);
    }

    for(int i=1;i<=n;++i)
        if(!viz[i]){

            dfs(i);
     //       p=0;
        }

    g<<rez.size()<<"\n";
    for(int i=0;i<rez.size();++i,g<<"\n")
        for(int j=0;j<rez[i].size();++j)
            g<<rez[i][j]<<" ";

    return 0;
}