Pagini recente » Cod sursa (job #3255993) | Cod sursa (job #628971) | Cod sursa (job #2878733) | Cod sursa (job #3258441) | Cod sursa (job #619969)
Cod sursa(job #619969)
#include<vector>
#include<fstream>
#define N 100010
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n,m,final[N],ordine[N],nr;
vector<int> g[N],gt[N],tc[N];
bool vizitat[N];
void df_final(int nod,int &timp) {
vector<int>::iterator i;
for(i=g[nod].begin();i!=g[nod].end();++i) if(!vizitat[*i]) {
vizitat[*i]=true;
df_final(*i,timp);
++timp;
}
final[nod]=timp;
}
void df(int nod) {
vector<int>::iterator i;
for(i=gt[nod].begin();i!=gt[nod].end();++i) if(!vizitat[*i]) {
vizitat[*i]=true;
tc[nr].push_back(*i);
df(*i);
}
}
int main() {
int i,a,b,timp=1;
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,timp);
}
for(i=1;i<=n;++i) {
ordine[n-final[i]+1]=i;
vizitat[i]=false;
}
for(i=1;i<=n;++i) if(!vizitat[ordine[i]]) {
vizitat[i]=true;
++nr;
tc[nr].push_back(i);
df(i);
}
out << nr << "\n";
vector<int>::iterator it;
for(i=1;i<=nr;++i) {
for(it=tc[i].begin();it!=tc[i].end();++it)
out << *it << " ";
out << "\n";
}
return 0;
}