Cod sursa(job #1773148)

Utilizator alexilasiAlex Ilasi alexilasi Data 7 octombrie 2016 16:34:45
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

vector <int> v,a[100001],b[100001],ans[100001];
short check[100001];
int check2[100001],i,n,m,x,y,h,j;

void dfs1(int x)
{
    int q=i;
    check2[x]=q;
    v.push_back(x);
    for(int i=0;i<a[x].size();i++)
        if(check2[a[x][i]]!=q)
            dfs1(a[x][i]);
}

void dfs2(int x)
{
    check2[x]=n+i;
    for(int j=0;j<b[x].size();j++)
        if(check2[b[x][j]]!=n+i)
            dfs2(b[x][j]);
}

int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        a[x].push_back(y);
        b[y].push_back(x);
    }
    for(i=1;i<=n;i++)
    {
        if(check[i]==0)
        {
            v.erase(v.begin(),v.end());
            dfs1(i);
            dfs2(i);
            ++h;
            for(j=0;j<v.size();j++)
                if(check2[v[j]]==n+i)
                    {
                    ans[h].push_back(v[j]);
                    check[v[j]]=-1;
                    }
        }
    }
    fout<<h<<'\n';
    for(i=1;i<=h;i++)
        {
        for(j=0;j<ans[i].size();j++)
            fout<<ans[i][j]<<" ";
        fout<<'\n';
        }
    fin.close();
    fout.close();
    return 0;
}