Pagini recente » Diferente pentru utilizator/darth_niculus intre reviziile 76 si 77 | Atasamentele paginii Poligon7 | Cod sursa (job #172663) | Borderou de evaluare (job #1524762) | Cod sursa (job #3344917)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m;
vector<vector<int>>a,t,ctc;
vector<int>ts;
vector<bool>viz;
void topsort(int nod) {
viz[nod]=true;
for (auto f:a[nod]) {
if (!viz[f]) topsort(f);
}
ts.push_back(nod);
}
void kosaraju(int nod,vector<int>&cc) {
cc.push_back(nod);
viz[nod]=true;
for (auto f:t[nod]) {
if (!viz[f]){
kosaraju(f,cc);
}
}
}
int main() {
fin>>n>>m;
a.resize(n+1);
t.resize(n+1);
viz.resize(n+1);
int x,y;
for (int i=1;i<=m;i++) {
fin>>x>>y;
a[x].push_back(y);
t[y].push_back(x);
}
for (int i=1;i<=n;i++) {
if (!viz[i]) {
topsort(i);
}
}
fill(viz.begin(),viz.end(),false);
reverse(ts.begin(),ts.end());
for (int i=0;i<n;i++) {
if (!viz[ts[i]]) {
vector<int>cur;
kosaraju(ts[i],cur);
ctc.push_back(cur);
}
}
fout<<ctc.size()<<'\n';
for (auto x:ctc) {
for (auto y:x) fout<<y<<" ";
fout<<'\n';
}
return 0;
}