Pagini recente » Cod sursa (job #1420117) | Cod sursa (job #326050) | Cod sursa (job #28460) | Cod sursa (job #1580360) | Cod sursa (job #3153619)
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in"); //ctc.in
ofstream fout("ctc.out");
vector <vector<int>> G;
vector <vector<int>> GT;
vector <bool> V;
vector <vector<int>> comp;
stack <int> s;
int n, m, cate;
void dfs(int x){
for(auto i: G[x]){
if(!V[i]){
V[i]=1;
dfs(i);
}
}
s.push(x);
//cout<<x<<' ';
}
void dfsGT(int x){
comp[cate].push_back(x);
//cout<<x<<' ';
for(auto i: GT[x]){
if(!V[i]){
V[i]=1;
dfsGT(i);
}
}
}
int main()
{
int x, y;
fin>>n>>m;
G = GT = vector<vector<int>>(n + 1);
for(int i=1; i<=m; i++){
fin>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
V=vector<bool> (n+1, false);
for(int i=1; i<=n; i++){
if(V[i]==false){
V[i]=1;
dfs(i);
}
}
V=vector<bool> (n+1, false);
comp = vector<vector<int>>(n+1);
while(!s.empty()){
x=s.top();
if(V[x]==false){
cate++;
V[x]=1;
dfsGT(x);
}
s.pop();
}
fout<<cate<<'\n';
for(int i=1; i<=cate; i++){
for(auto j: comp[i]){
fout<<j<<' ';
}
fout<<'\n';
}
fin.close();
fout.close();
return 0;
}