Pagini recente » Cod sursa (job #2285955) | Cod sursa (job #1008707) | Cod sursa (job #739332) | Cod sursa (job #2059603) | Cod sursa (job #622600)
Cod sursa(job #622600)
#include<fstream>
#include<vector>
#include<algorithm>
#define N 50010
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];
void df_final(int nod) {
vector<int>::iterator i;
for(i=g[nod].begin();i!=g[nod].end();++i) if(!vizitat[*i]) {
vizitat[*i]=true;
df_final(*i);
}
ordine[++nr]=nod;
}
void df(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);
}
}
bool cmp(vector<int> a, vector<int> b) {
vector<int>::iterator it;
int min=1<<20,min2=1<<20;
for(it=a.begin();it!=a.end();++it)
if(*it<min)
min=*it;
for(it=b.begin();it!=b.end();++it)
if(*it<min2)
min2=*it;
return min<min2;
}
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]) {
vizitat[i]=true;
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;
//sort(&ctc[1],&ctc[nrc+1],cmp);
for(i=1;i<=nrc;++i) {
for(it=ctc[i].begin();it!=ctc[i].end();++it)
out << *it << " ";
out << "\n";
}
return 0;
}