Cod sursa(job #2678612)

Utilizator raducostacheRadu Costache raducostache Data 28 noiembrie 2020 14:25:43
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
//
//  main.cpp
//  ctc
//
//  Created by Radu Costache on 28/11/2020.
//  Copyright © 2020 Radu Costache. All rights reserved.
//

#include <fstream>
#include <vector>
#include <bitset>

#define NMAX 100005

using namespace std;

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

int n, m, ctc;

vector <int> v1[NMAX];
vector <int> v2[NMAX];
vector <int> ans[NMAX];

void dfs1(int);
void dfs2(int);

bitset <NMAX> viz;
bitset <NMAX> viz1;
bitset <NMAX> viz2;


int main(int argc, const char * argv[]) {
    // insert code here...
    f >> n;
    f >> m;
    while (m--) {
        int x, y;
        f >> x >> y;
        v1[x].push_back(y);
        v2[y].push_back(x);
    }
    for (int i = 1; i <= n; ++i) {
        if (!viz[i]) {
            ++ctc;
            viz1.reset();
            dfs1(i);
            viz2.reset();
            dfs2(i);
        }
    }
    g << ctc << '\n';
    for (int i = 1; i <= ctc; ++i) {
        for (auto it:ans[i])
            g << it << ' ';
        g << '\n';
    }
    return 0;
}

void dfs1(int node) {
    viz1[node] = 1;
    for (auto it:v1[node])
        if (viz1[it] == 0 && viz[it] == 0) {
            dfs1(it);
        }
}

void dfs2(int node) {
    viz2[node] = 1;
    if (viz1[node] == 1) {
        ans[ctc].push_back(node);
        viz[node] = 1;
    }
    for (auto it:v2[node])
        if (viz2[it] == 0 && viz[it] == 0) {
            dfs2(it);
        }
}