Pagini recente » Cod sursa (job #2806259) | Cod sursa (job #2327436) | Cod sursa (job #1861854) | Cod sursa (job #860285) | Cod sursa (job #1909659)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 100005
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n,m,x,y,d[NMAX],viz[NMAX],contor,componenta;
vector<int> a[NMAX];
vector<int> t[NMAX];
vector<int> sol[NMAX];
void dfs(int nod) {
viz[nod] = 1;
for(int i=0;i<a[nod].size();i++) {
if(!viz[a[nod][i]]) {
dfs(a[nod][i]);
}
}
d[contor++] = nod;
}
void dfst(int nod) {
viz[nod] = 1;
for(int i=0;i<t[nod].size();i++) {
if(!viz[t[nod][i]]) {
dfst(t[nod][i]);
}
}
sol[componenta].push_back(nod);
}
int main()
{
in >> n >> m;
for(int i=0;i<m;i++) {
in >> x >> y;
a[x].push_back(y);
t[y].push_back(x);
}
// for(int i=1;i<=n;i++) {
// for(int j=0;j<a[i].size();j++) {
// cout << i << "->>> " << a[i][j] << " ";
// }
// cout << endl;
// }
for(int i=1;i<=n;i++) {
if(!viz[i]) {
dfs(i);
}
}
for(int i=1;i<=n;i++) {
viz[i] = 0;
}
for(int i=n-1;i>=0;i--) {
if(!viz[d[i]]) {
dfst(d[i]);
//cout << d[i] << " ";
componenta++;
//cout << 1 << " ";
}
}
out << componenta << "\n";
for(int i=0;i<componenta;i++) {
sort(sol[i].begin(),sol[i].end());
for(int j=0;j<sol[i].size();j++) {
out<< sol[i][j] << " ";
}
out << "\n";
}
return 0;
}