Cod sursa(job #2937461)

Utilizator Samoila_AlexandruSamoilaAlexandru Samoila_Alexandru Data 10 noiembrie 2022 14:27:24
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int nMax=1e5+5;

vector<vector<int> > g, gt;
vector<int> v;
vector<int> f;

void dfsG(int k)
{
    v[k]=1;
    for(auto i : g[k])
        if(!v[i])
        dfsG(i);
    f.push_back(k);
}

void dfsGT(int k, int val)
{
    v[k]=val;
    for(auto i : gt[k])
        if(!v[i])
        dfsGT(i, val);
}

int n, m, cnt;

int main()
{
    fin>>n>>m;
    int x, y;

    g=gt=vector<vector<int>>(n+1);

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

    fin.close();

    v=vector<int>(n+1, 0);

    for(int i=1; i<=n; i++)
        if(!v[i])
        dfsG(i);

    v=vector<int>(n+1, 0);

    for(vector<int>::reverse_iterator it=f.rbegin(); it!=f.rend(); it++)
        if(!v[*it])
    {
        cnt++;
        dfsGT(*it, cnt);
    }

    fout<<cnt<<'\n';

    for(int i=1; i<=cnt; i++)
    {
        for(int j=1; j<=n; j++)
            if(v[j]==i)
            fout<<j<<' ';
        fout<<'\n';
    }

    fout.close();

    return 0;
}