Cod sursa(job #1791852)

Utilizator andrei1299Ghiorghe Andrei Alexandru andrei1299 Data 29 octombrie 2016 19:40:01
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;
int n,m,st[100001],top,nr;
vector <int> L1[100001],L2[100001],sol[100001];
bool viz[100001];


void dfs1(int nod)
{
    viz[nod]=1;
    for(unsigned int  i=0;i<L1[nod].size();i++)
        if(viz[L1[nod][i]]==0)
            dfs1(L1[nod][i]);
    st[++top]=nod;
}

void dfs2(int nod)
{
    viz[nod]=0;
    for(unsigned int i=0;i<L2[nod].size();i++)
        if(viz[L2[nod][i]]==1)
            dfs2(L2[nod][i]);
    sol[nr].push_back(nod);
}

int main()
{
    int x,y;
    int i;
    unsigned k;
    ifstream fin("ctc.in");
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        L1[x].push_back(y);
        L2[y].push_back(x);
    }
    fin.close();
    for(i=1;i<=n;i++)
        if(viz[i]==0)
            dfs1(i);
    while(top>0)
    {
        if(viz[st[top]]==1)
        {
            nr++;
            dfs2(st[top]);
        }
         top--;
    }

    ofstream fout("ctc.out");
    fout<<nr<<"\n";
    for(i=1;i<=n;i++)
    {
        for(k=0;k<sol[i].size();k++)
            fout<<sol[i][k]<<" ";
        fout<<"\n";
    }
    fout.close();
    return 0;
}