Pagini recente » Cod sursa (job #1293149) | Cod sursa (job #1257792) | Cod sursa (job #1281388) | Cod sursa (job #757085) | Cod sursa (job #1665154)
#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
int n, m;
vector<int> g[N], gt[N];
bool vis[N];
int cind[N];
vector<int> procList;
vector<int> scc[N];
void firstPass(const int &cur) {
vis[cur] = true;
for(const auto nxt : g[cur]) {
if(vis[nxt] == false) {
firstPass(nxt);
}
}
procList.push_back(cur);
}
void secondPass(const int &cur, const int &component) {
cind[cur] = component;
scc[component].push_back(cur);
for(const auto nxt : gt[cur]) {
if(cind[nxt] == 0) {
secondPass(nxt, component);
}
}
}
int main() {
ifstream in("ctc.in");
ofstream out("ctc.out");
int i, x, y, ind;
in >> n >> m;
for(i = 1; i <= m; i++) {
in >> x >> y;
g[x].push_back(y);
gt[y].push_back(x);
}
ind = 0;
for(i = 1; i <= n; i++) {
if(vis[i] == false) {
firstPass(i);
}
}
for(i = n - 1; i >= 0; i--) {
if(cind[procList[i]] == 0) {
++ind;
secondPass(procList[i], ind);
}
}
out << ind << '\n';
for(i = 1; i <= ind; i++) {
for(const auto j : scc[i]) {
out << j << ' ';
}
out << '\n';
}
return 0;
}