Mai intai trebuie sa te autentifici.
Cod sursa(job #3271036)
| Utilizator | 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;
}
