Cod sursa(job #2924717)

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

using namespace std;

int p[100001], mn[100001], ctc[100001], n, m, nr;
vector <int> l[100001], t[100001];

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

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

void df2 (int vf)
{
    int i;
    mn[vf] = 1;
    for (i = 0; i < t[vf].size(); i++)
        if (mn[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 (ctc[i] == 0)
    {
        for (j = 1; j <= n; j++)
            p[j] = mn[j] = 0;
        nr++;
        df1(i);
        df2(i);
        for (j = 1; j <= n; j++)
            if (p[j] == mn[j] == 1) ctc[j] = nr;
    }
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;
}