Cod sursa(job #3166630)

Utilizator dimitriemihaiMihai Dimitrie dimitriemihai Data 9 noiembrie 2023 09:58:21
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>
#define NM 100001

using namespace std;

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

vector <int> g[NM], gt[NM], ctc[NM];
int n, m, contor, k, viz[NM], z[NM], nrc;

void dfs (int x)
{
    int w, j;

    viz[x] = 1;
    for (j = 0; j < g[x].size(); j++)
    {
        w = g[x][j];
        if (viz[w] == 0)
            dfs(w);
    }

    k++;
    z[k] = x;
}

void dfst (int x)
{
    int w, j;

    viz[x] = 1;
    ctc[nrc].push_back(x);

    for (j = 0; j < gt[x].size(); j++)
    {
        w = gt[x][j];
        if (viz[w] == 0)
            dfst(w);
    }
}

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

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

    for (i = 1; i <= n; i ++)
        if (viz[i] == 0)
            dfs(i);

    for (i = 1; i <= n; i ++)
        viz[i] = 0;

    for (i = n; i >= 1; i --)
        if (viz[z[i]] == 0)
        {
            nrc ++;
            dfst(z[i]);
        }

    fout << nrc << '\n';

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


    return 0;
}