Cod sursa(job #2924715)

Utilizator DafinaTrufasTrufas Dafina DafinaTrufas Data 9 octombrie 2022 11:24:49
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include<bits/stdc++.h>

using namespace std;

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

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

void df (int vf)
{
    int i;
    v[vf] = nr;
    for (i = 0; i < l[vf].size(); i++)
        if (v[l[vf][i]] == 0 && find(l[l[vf][i]].begin(), l[l[vf][i]].end(), vf) != l[l[vf][i]].end())
            df(l[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);
}
for (k = 1; k <= n; k++)
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if(find(l[i].begin(), l[i].end(), j) == l[i].end() && find(l[i].begin(), l[i].end(), k) != l[i].end() && find(l[k].begin(), l[k].end(), j) != l[k].end())
                l[i].push_back(j);
for (i = 1; i <= n; i++)
{
    if (v[i] == 0)
    {
        nr++;
        df(i);
    }
}
g << nr << '\n';
for (i = 1; i <= nr; i++)
{
    for (j = 1; j <= n; j++)
        if (v[j] == i) g << j << ' ';
    g << '\n';
}
return 0;
}