Cod sursa(job #2205529)

Utilizator ioana_marinescuMarinescu Ioana ioana_marinescu Data 19 mai 2018 14:18:20
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>
#include <algorithm>
const int MAX_V = 100000;
using namespace std;

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

int V, E;
vector<int> neighbours[MAX_V + 1];
vector<int> neighboursT[MAX_V + 1];
vector<int> L;
vector<int> vertices[MAX_V + 1];

bool visited[MAX_V + 1];
int ctcCount;

void dfs(int u) {
    visited[u] = true;
    for (int v : neighbours[u])
        if (!visited[v])
        dfs(v);
    L.push_back(u);
}

void dfsT(int u) {
    visited[u] = true;
    for (int v : neighboursT[u])
        if (!visited[v])
            dfsT(v);
    vertices[ctcCount].push_back(u);
}

int main() {
    fin >> V >> E;
    for (int i = 0; i < E; i++) {
        int u, v;
        fin >> u >> v;
        neighbours[u].push_back(v);
        neighboursT[v].push_back(u);
    }

    for (int u = 1; u <= V; u++)
        if (!visited[u])
            dfs(u);

    reverse(L.begin(), L.end());

    for (int u : L)
        visited[u] = false;
    for (int u : L)
        if (!visited[u]) {
            ctcCount++;
            dfsT(u);
        }

    fout << ctcCount << '\n';
    for (int i = 1; i <= ctcCount; i++) {
        for (int u : vertices[i])
            fout << u << ' ';
        fout << '\n';
    }
    return 0;
}