Pagini recente » Cod sursa (job #336806) | Cod sursa (job #3201441) | Cod sursa (job #1978951) | Cod sursa (job #2330912) | Cod sursa (job #3240306)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, x, y;
vector<vector<int> > G, GT, componente;
vector<int> comp, viz;
stack<int> order;
void dfs(int start){
viz[start] = 1;
for(int x : G[start])
if(!viz[x])
dfs(x);
order.push(start);
}
void dfsT(int start){
viz[start] = 1;
comp.push_back(start);
for(int x : GT[start])
if(!viz[x])
dfsT(x);
}
int main(){
fin >> n >> m;
G.resize(n + 1);
GT.resize(n + 1);
viz.resize(n + 1);
for(;m--;){
fin >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
for(int i = 1; i <= n; ++i)
if(!viz[i])
dfs(i);
viz = vector<int>(n + 1);
for(;!order.empty(); order.pop())
if(!viz[order.top()]){
dfsT(order.top());
componente.push_back(comp);
comp.clear();
}
fout << componente.size() << '\n';
for(auto c : componente){
for(int x : c)
fout << x << ' ';
fout << '\n';
}
}