Cod sursa(job #2925796)

Utilizator Teodor94Teodor Plop Teodor94 Data 16 octombrie 2022 03:43:51
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <bits/stdc++.h>
using namespace std;

#define NO_NODES 100000

int noNodes;
vector<int> graph[NO_NODES];
vector<int> revGraph[NO_NODES];

char marked[NO_NODES];
vector<int> visited;

vector<int> components[NO_NODES];

void addEdge(int x, int y) {
    graph[x].push_back(y);
    revGraph[y].push_back(x);
}

void resetVisited() {
    for (int node : visited)
        if (marked[node] == 1)
            marked[node] = 0;
    visited.clear();
}

void dfs(vector<int>* graph, vector<int>& visited, int node, char mark) {
    marked[node] = mark;
    visited.push_back(node);

    for (int neighbour : graph[node])
        if (marked[neighbour] == mark - 1)
            dfs(graph, visited, neighbour, mark);
}

int main() {
    FILE *fin, *fout;
    fin = fopen("ctc.in", "r");
    fout = fopen("ctc.out", "w");

    int noEdges, noComponents;
    int x, y;

    fscanf(fin, "%d%d", &noNodes, &noEdges);
    while (noEdges--) {
        fscanf(fin, "%d%d", &x, &y);
        addEdge(x - 1, y - 1);
    }

    noComponents = 0;
    for (x = 0; x < noNodes; ++x) 
        if (!marked[x]) {
            dfs(graph, visited, x, 1);
            dfs(revGraph, components[noComponents], x, 2);
            ++noComponents;

            resetVisited();
        }

    fprintf(fout, "%d\n", noComponents);
    for (x = 0; x < noComponents; ++x, fputc('\n', fout))
        for (int node : components[x])
            fprintf(fout, "%d ", node + 1);

    fclose(fin);
    fclose(fout);
    return 0;
}