Pagini recente » Statistici Tiron Filip (t.fippy) | Clasament Adobe - Code Pandas, Runda 1 | Profil c909056 | Profil Boddy | Cod sursa (job #3271036)
#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;
}