Pagini recente » Cod sursa (job #216588) | Cod sursa (job #917389) | Cod sursa (job #2164245) | Cod sursa (job #1705336) | Cod sursa (job #3270170)
#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;
}