Cod sursa(job #2886227)

Utilizator iulianarsenoiuArsenoiu Iulian iulianarsenoiu Data 7 aprilie 2022 13:51:15
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

int n,m;

bool sel[100005];

vector<int> G[100005],B[100005];

vector<int> l;

int nr;

vector<int> rez[100005];

void dfs(int nod)
{
    sel[nod] = true;
    for(auto it : G[nod])
    {
        if(sel[it])
        {
            continue;
        }
        dfs(it);
    }
    l.push_back(nod);
}

void top_sort()
{
    for(int i=1;i<=n;i++)
    {
        if(!sel[i])
        {
            dfs(i);
        }
    }
    reverse(l.begin(),l.end());
}

void dfs2(int nod)
{
    rez[nr].push_back(nod);
    sel[nod] = true;
    for(auto it : B[nod])
    {
        if(sel[it])
        {
            continue;
        }
        dfs2(it);
    }
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        f>>x>>y;
        G[x].push_back(y);
        B[y].push_back(x);
    }
    top_sort();
    memset(sel,0,sizeof(sel));
    for(auto it : l)
    {
        if(!sel[it])
        {
            ++nr;
            dfs2(it);
        }
    }
    g<<nr<<'\n';
    for(int i=1;i<=nr;i++)
    {
        for(auto it : rez[i])
        {
            g<<it<<' ';
        }
        g<<'\n';
    }
    return 0;
}