Cod sursa(job #2924718)

Utilizator DafinaTrufasTrufas Dafina DafinaTrufas Data 9 octombrie 2022 12:45:20
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;

int v[100001], ctc[100001], n, m, nr;
vector <int> l[100001], t[100001], fin;

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

void df1 (int vf)
{
    int i;
    v[vf] = 1;
    for (i = 0; i < l[vf].size(); i++)
        if (v[l[vf][i]] == 0)
            df1(l[vf][i]);
    fin.push_back(vf);
}

void df2 (int vf)
{
    int i;
    v[vf] = 1;
    ctc[vf] = nr;
    for (i = 0; i < t[vf].size(); i++)
        if (v[t[vf][i]] == 0)
            df2(t[vf][i]);
}

int main()
{int i, j, k;
f >> n >> m;
for (k = 1; k <= m; k++)
{
    f >> i >> j;
    l[i].push_back(j);
    t[j].push_back(i);
}
for (i = 1; i <= n; i++)
    if (v[i] == 0) df1(i);
for (i = 1; i <= n; i++) v[i] = 0;
for (i = fin.size() - 1; i >= 0; i--)
    if (v[fin[i]] == 0)
        {
            nr++;
            df2(fin[i]);
        }
g << nr << '\n';
for (i = 1; i <= nr; i++)
{
    for (j = 1; j <= n; j++)
        if (ctc[j] == i) g << j << ' ';
    g << '\n';
}
return 0;
}