Cod sursa(job #3271036)

Utilizator EnnBruhEne Andrei EnnBruh Data 25 ianuarie 2025 09:10:43
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const string fileName = "ctc";
ifstream in  (fileName + ".in");
ofstream out (fileName + ".out");

const int maxSize = 102;
const int inf = 0x3f3f3f3f;

vector <int> adj[maxSize], rev[maxSize], nodesInComponent[maxSize], after;
bitset <maxSize> visited;
void depthSearch(int node) {
    visited[node] = true;
    for (auto nxt : adj[node]) {
        if (visited[nxt]) continue ;
        visited[nxt] = true; depthSearch( nxt );
    }
    after.emplace_back( node );
}

int numComponents;
void revSearch(int node) {
    visited[node] = false; nodesInComponent[numComponents].push_back( node );
    for (auto nxt : rev[node]) {
        if (!visited[nxt]) continue ;
        revSearch( nxt );
    }
}

int main( ) {
    int numNodes, numEdges; in >> numNodes >> numEdges;
    int nodeA, nodeB;
    for (int i = 0; i < numEdges; ++i) {
        in >> nodeA >> nodeB;
        adj[nodeA].push_back( nodeB );
        rev[nodeB].push_back( nodeA );
    }

    after.reserve(numEdges + 1);
    for (int node = 1; node <= numNodes; ++node)
        if (!visited[node]) depthSearch( node );

    for (auto node = after.rbegin( ); node != after.rend( ); ++node)
        if (visited[*node]) {
                ++numComponents;
                revSearch( *node );
        }

    out << numComponents << endl;
    for (int i = 1; i <= numComponents; ++i, out << endl)
        for (auto node : nodesInComponent[i]) out << node << ' ';
    return 0;
}