Pagini recente » Cod sursa (job #3244112) | Cod sursa (job #3251160) | Cod sursa (job #2745703) | Cod sursa (job #2536920) | Cod sursa (job #1117891)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
const int NMAX = 100009;
int N; vector<int> G[NMAX], GT[NMAX]; int ord[NMAX];bool viz[NMAX];
vector<vector<int> > Conex;
int M;
void dfs(int nod) {
viz[nod] = true;
for(unsigned i = 0;i < G[nod].size(); ++i)
if(viz[G[nod][i]] == false) dfs(G[nod][i]);
ord[++ord[0]] = nod;
}
void dfs2(int nod) {
viz[nod] = true;
Conex[Conex.size() - 1].push_back(nod);
for(unsigned i = 0 ;i < GT[nod].size(); ++i)
if(viz[GT[nod][i]] == false)
dfs2(GT[nod][i]);
}
int main() {
fin >> N >> M;
for(int i = 1; i <= M; ++i){
int a, b;
fin >> a >> b;
G[a].push_back(b);
GT[b].push_back(a);
}
for(int i = 1; i<= N; ++i)
if(viz[i] == false)
dfs(i);
memset(viz, false, sizeof(viz));
for(int i = N; i >= 1; --i) {
if(viz[ord[i]] == false) {
Conex.push_back(vector<int>(0));
dfs2(ord[i]);
}
}
fout << Conex.size() <<'\n';
for(unsigned i = 0 ;i < Conex.size(); ++i) {
for(unsigned j = 0 ;j < Conex[i].size(); ++j)
fout << Conex[i][j] <<" " ;
fout << '\n';
}
return 0;
}