Cod sursa(job #3270170)

Utilizator EnnBruhEne Andrei EnnBruh Data 22 ianuarie 2025 12:25:46
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 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 = 100002;
const int inf = 0x3f3f3f3f;

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

int numComponents;
void revSearch(int node) {
        for (auto nxt : rev[node]) {
                if (visited[nxt]) continue ;
                visited[nxt] = true;
                nodesInComponent[numComponents].push_back( nxt );
                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 );
        }

        post.reserve(numNodes + 1);

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

        visited = 0;
        for (auto node = post.rbegin( ); node != post.rend( ); ++node) {
                if (visited[*node]) continue ;
                ++numComponents;
                visited[*node] = true; nodesInComponent[numComponents].push_back( *node );
                revSearch( *node );
        }

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