Pagini recente » Cod sursa (job #821403) | Cod sursa (job #2219310) | Cod sursa (job #1406012) | Cod sursa (job #2604728) | Cod sursa (job #623120)
Cod sursa(job #623120)
#include<fstream>
#include<vector>
#define N 100010
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n,m,ordine[N],nrc,nr;
vector<int> g[N],ctc[N],gt[N];
bool vizitat[N];
inline void df_final(const int &nod) {
vector<int>::iterator i;
vizitat[*i]=true;
for(i=g[nod].begin();i!=g[nod].end();++i) if(!vizitat[*i])
df_final(*i);
ordine[++nr]=nod;
}
inline void df(const int &nod) {
vector<int>::iterator i;
vizitat[nod]=true;
for(i=gt[nod].begin();i!=gt[nod].end();++i) if(!vizitat[*i]) {
ctc[nrc].push_back(*i);
df(*i);
}
}
int main() {
int i,a,b;
in >> n >> m;
for(i=1;i<=m;++i) {
in >> a >> b;
g[a].push_back(b);
gt[b].push_back(a);
}
for(i=1;i<=n;++i) if(!vizitat[i])
df_final(i);
for(i=1;i<=n;++i)
vizitat[i]=false;
for(i=n;i!=0;--i) if(!vizitat[ordine[i]]) {
++nrc;
ctc[nrc].push_back(ordine[i]);
df(ordine[i]);
}
out << nrc << "\n";
vector<int>::iterator it;
for(i=1;i<=nrc;++i) {
for(it=ctc[i].begin();it!=ctc[i].end();++it)
out << *it << " ";
out << "\n";
}
return 0;
}