Cod sursa(job #1807182)

Utilizator StormLawGorea Ioan StormLaw Data 16 noiembrie 2016 09:27:19
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

struct nod
{
    int viz=0;

    vector <int> v;
    vector <int> iv;
};

int n, m;

nod g[100001];
int comp[100001];
vector <int> a[100001];
int nc, k;

void dfs(int x)
{
    g[x].viz=1;
    for(int i=0; i<g[x].v.size(); i++)
        if(g[g[x].v[i]].viz==0)
            dfs(g[x].v[i]);

    comp[++nc]=x;
}

void idfs(int x)
{
    g[x].viz=-1;
    a[k].push_back(x);
    for(int i=0; i<g[x].iv.size(); i++)
        if(g[g[x].iv[i]].viz==1)
            idfs(g[x].iv[i]);
}

int main()
{
    fin >> n >> m;

    for(int i=1; i<=m; i++)
    {
        int x, y;

        fin >> x >> y;

        g[x].v.push_back(y);
        g[y].iv.push_back(x);
    }

    for(int i=1; i<=n; i++)
    {
        if(g[i].viz==0)
            dfs(i);
    }

    for(int i=n; i>=1; i--)
    {
        if(g[comp[i]].viz==1)
        {
            k++;
            idfs(comp[i]);
        }
    }

    fout << k << '\n';

    for(int i=1; i<=k; i++)
    {
        for(int j=0; j<a[i].size(); j++)
            fout << a[i][j] << " ";

        fout << '\n';
    }

    return 0;
}