Cod sursa(job #2693983)

Utilizator WilIiamperWilliam Damian Balint WilIiamper Data 7 ianuarie 2021 19:13:03
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <vector>

using namespace std;

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

int n, m, ctc, vis[100001], arr[100001];

vector <int> G [100001];
vector <int> Gt[100001];

vector <int> sol[100001];

void DFS ( int nod, int Graf ) {
    vis[ nod ] += Graf;

    int size = Graf == 5 ? G[nod].size() : Gt[nod].size();
    for ( int l = 0; l < size; l++ ) {

        int to = Graf == 5 ? G[nod][l] : Gt[nod][l];
        if ( !vis[to] || ( ( Graf != 5 && vis[to] == 5 ) ) )
            DFS ( to, Graf );
    }
}

void Clear () {

    for (int i = 1; i <= n; i++)
        vis[i] = 0;
}

void solve () {

    for ( int i = 1; i <= n; i++ ) {
        if ( !arr[i] ) {
            DFS (i, 5);
            DFS (i, -3);

            ctc++;
            for ( int j = 1; j <= n; j++ ) {
                if ( vis[j] == 2 ) {
                    sol[ctc].push_back(j);
                    arr[j] = 1;
                }
            }

            Clear();
        }
    }
}

void write () {

    fout << ctc << "\n";
    for (int i = 1; i <= ctc; i++) {
        for ( unsigned int l = 0; l < sol[i].size(); l++ ) {
            fout << sol[i][l] << " ";
        }
        fout << "\n";
    }
}

void read () {
    fin >> n >> m;

    int from, to;
    for (int i = 1; i <= m; i++) {
        fin >> from >> to;
        G[ from ].push_back (to);
        Gt[ to ].push_back (from);
    }
}

int main()
{
    read ();
    solve ();
    write ();
    return 0;
}