Cod sursa(job #3349225)

Utilizator LukiLuckObretin Luca Andrei LukiLuck Data 26 martie 2026 16:11:48
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m, i, k, x, y, nr =0, s = 0;

vector<int>  gr[100001], grt[100001], ctc[100001];
bool v[100001];
int st[100001];

void dfs(int k)
{
    v[k] = true;
    for(int j =0; j< gr[k].size(); j++){
        if(v[gr[k][j]] == false){
            dfs(gr[k][j]);
        }
    }
    s++;
    st[s] = k;
}

void tdfs(int k)
{
    v[k] = true;
    for(int j =0; j< grt[k].size(); j++){
        if(v[grt[k][j]] == false){
            tdfs(grt[k][j]);
        }
    }
    ctc[nr].push_back(k);



}

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

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


    for(i =1; i<=n; i++){
        v[i] = false;
    }

    for(i = 1; i<= n; i++){
        if(v[i] == false){
            dfs(i);
        }
    }

    for(i =1; i<=n; i++){
        v[i] = false;
    }

    for(i = s; i>= 1; i--){
        if(v[st[i]] == false){
            nr++;
            tdfs(st[i]);
        }
    }

    fout<<nr<<endl;

    for(i = 1; i<=n; i++){
        for(int j =0; j<ctc[i].size(); j++){
            fout<<ctc[i][j]<<" ";
        }
        fout<<endl;
    }
}