Pagini recente » Cod sursa (job #2175718) | Cod sursa (job #2201246) | Cod sursa (job #2957788) | Cod sursa (job #1363591) | Cod sursa (job #2232045)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#define MAXN 100005
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<int>graf[MAXN],graf_transpus[MAXN],ans[MAXN];
queue<int>discovered;
bool viz[MAXN];
int n,m,cnt;
void init(){
cnt = 0;
for(int i = 0; i < MAXN; i++)
viz[i] = false;
}
void dfs1(int start){
viz[start] = true;
int curent;
for(int i = 0; i < graf[start].size(); i++){
curent = graf[start][i];
if(!viz[curent])
dfs1(curent);
}
discovered.push(start);
}
void dfs2(int start){
viz[start] = true;
int curent;
ans[cnt].push_back(start);
for(int i = 0; i < graf_transpus[start].size(); i++){
curent = graf[start][i];
if(!viz[curent])
dfs2(curent);
}
}
int main()
{
in>>n>>m;
for(int i = 1; i <= m; i++){
int nod,muchie;
in>>nod>>muchie;
graf[nod].push_back(muchie);
graf_transpus[muchie].push_back(nod);
}
for(int i = 1; i <= n; i++)
if(!viz[i])
dfs1(i);
init();
while(!discovered.empty()){
int nod = discovered.front();
discovered.pop();
if(!viz[nod]){
dfs2(nod);
cnt++;
}
}
out<<cnt<<"\n";
for(int i = 0; i < cnt; i++){
for(int j = 0; j < ans[i].size(); j++)
out<<ans[i][j]<<" ";
out<<"\n";
}
return 0;
}