Cod sursa(job #1874878)

Utilizator mihnea00Duican Mihnea mihnea00 Data 10 februarie 2017 15:26:06
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
//componente tari conexe cu tarjan ;)
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int i,n,j,m,x,y,nr,k,vp[100010],vm[100010];
vector<int> af[100010],l[100010],*it,sti;
bool viz[100010],vizsti[100010];

void tarjan(int x)
{
    viz[x]=1;
    sti.push_back(x);
    vizsti[x]=1;
    for(int i=0;i<l[x].size();++i)
    {
        if(viz[l[x][i]]==0)
        {
            ++k;
            vp[l[x][i]]=k;
            vm[l[x][i]]=k;
            tarjan(l[x][i]);
            vm[x]=min(vm[x],vm[l[x][i]]);
        }
        else
        {
            if(vizsti[l[x][i]])
                vm[x]=min(vm[x],vm[l[x][i]]);
        }
    }

    if(vm[x]==vp[x])
    {
        ++nr;
        while(sti.back()!=x)
        {
            af[nr].push_back(sti.back());
            vizsti[sti.back()]=0;
            sti.pop_back();
        }
        af[nr].push_back(x);
        vizsti[x]=0;
        sti.pop_back();
    }
}

int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y;
        l[x].push_back(y);
    }

    for(i=1;i<=n;++i)
    {
        if(viz[i]==0)
            tarjan(i);
    }

    fout<<nr<<"\n";

    for(i=1;i<=nr;++i)
    {
        for(j=0;j<af[i].size();++j)
            fout<<af[i][j]<<" ";
        fout<<"\n";
    }
    return 0;
}