Cod sursa(job #2367229)

Utilizator BlkAlexAlex Negru BlkAlex Data 5 martie 2019 09:38:54
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>
#define MAX 5100

using namespace std;

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

int n, m;
int viz[MAX];
int c[MAX], nrc;
vector <int> G[MAX];
vector <int> Gi[MAX];
vector <int> rez[MAX];

void dostuff(){
    f >> n >> m;
    for (int i = 1; i <= m; ++i){
        int x, y;
        f >> x >> y;
        G[x].push_back(y);
        Gi[y].push_back(x);
    }
}

void dfs(int node){
    viz[node]++;
    for (int i = 0; i < G[node].size(); ++i){
        int newnode = G[node][i];
        if (viz[newnode] == 0){
            dfs(newnode);
        }
    }
}

void dfsi(int node){
    viz[node]++;
    for (int i = 0; i < Gi[node].size(); ++i){
        int newnode = Gi[node][i];
        if (viz[newnode] == 1){
            dfsi(newnode);
        }
    }
}

void afish(){
    g << nrc << '\n';
    for (int i = 1; i <= nrc; i++){
        for (int j = 0; j < rez[i].size(); j++){
            g << rez[i][j] << ' ';
        }
        g << '\n';
    }
}

void domorestuff(){
    for (int i = 1; i <= n; ++i){
        if (viz[i] == 0){
            nrc++;
            dfs(i);
            dfsi(i);
            for (int j = 1; j <= n; j++){
                if (viz[j] == 2){
                    viz[j] = -1;
                    rez[nrc].push_back(j);
                }
                if (viz[j] != -1){
                    viz[j] = 0;
                }
            }
        }
    }
    afish();
}

int main()
{
    ios_base::sync_with_stdio(false);
    dostuff();
    domorestuff();
    return 0;
}