Pagini recente » cerculetz_01 | Cod sursa (job #2282124) | Cod sursa (job #2049175) | Cod sursa (job #2216717) | Cod sursa (job #2974517)
//kosaraju
#include <fstream>
#include <vector>
#include <stack>
#define nmax 100010
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, vis1[nmax], vis2[nmax], c1, c2;
vector <int> g[nmax];
vector <int> gt[nmax];
vector <vector<int>> ctc;
stack <int> s;
void dfs1(int i){
vis1[i] = c1;
for(auto j : g[i])
if(!vis1[j])
dfs1(j);
s.push(i);
}
void dfs2(int i){
vis2[i] = c2;
for(auto j : gt[i])
if(!vis2[j])
dfs2(j);
}
int main()
{
fin >> n >> m;
for(int i=1; i<=m; i++){
int x, y;
fin >> x >> y;
g[x].push_back(y);
gt[y].push_back(x);
}
for(int i=1; i<=n; i++)
if(!vis1[i]){
c1++;
dfs1(i);
}
while(!s.empty()){
int x=s.top();
s.pop();
if(!vis2[x]){
c2++;
dfs2(x);
}
}
ctc.clear();
ctc.resize(c2);
for(int i=1; i<=n; i++)
ctc[vis2[i]-1].push_back(i);
fout << ctc.size() << '\n';
for(auto &i : ctc){
for(auto &j : i)
fout << j << ' ';
fout << '\n';
}
return 0;
}