Pagini recente » Cod sursa (job #436960) | Cod sursa (job #1768528) | Cod sursa (job #798948) | Cod sursa (job #344738) | Cod sursa (job #571195)
Cod sursa(job #571195)
#include<iostream>
#include<fstream>
#include<list>
using namespace std;
list<int> a[10000];
list<int> b[10000];
list<int> c[10000];
void dfsN(list<int> *l,int vf,list<int>& stiva,int *color)
{
color[vf] = 1;
list<int>::iterator it;
for(it = l[vf].begin() ; it != l[vf].end() ; it++)
if(color[*it] == 0)
dfsN(l,*it,stiva,color);
stiva.push_front(vf);
color[vf] = 2;
}
void dfsT(list<int> *l,int vf,list<int>& stiva,int *color)
{
color[vf] = 1;
stiva.push_front(vf);
list<int>::iterator it;
for(it = l[vf].begin() ; it != l[vf].end() ; it++)
if(color[*it] == 0)
dfsN(l,*it,stiva,color);
color[vf] = 2;
}
void ctc(list<int> *a,list<int> *c,list<int> stiva,int n)
{
int *color = new int[n + 1];
for(int i = 1 ; i <= n ;i++)
color[i] = 0;
for(int i = 1 ; i <= n ; i++)
{
if(color[i] == 0)
dfsN(a,i,stiva,color);
}
cout<<endl;
for(int i = 1 ; i <= n ;i++)
color[i] = 0;
int l = 0;
while(stiva.empty() != true)
{
int p = stiva.front();
stiva.pop_front();
if(color[p] == 0)
dfsT(c,p,b[l],color);
l++;
}
fstream out("ctc.out",ios::out);
out<<l<<endl;
for(int i = 0 ; i < l ; i++)
{
list<int>::iterator it;
for(it = b[i].begin() ; it != b[i].end() ; it++)
out<<*it<<" ";
out<<endl;
}
}
int main()
{
fstream in("ctc.in",ios::in);
int n,m;
in>>n;
in>>m;
for(int i = 1 ; i <= m ; i++)
{
int k1,k2;
in>>k1;
in>>k2;
a[k1].push_front(k2);
c[k2].push_front(k1);
}
list<int> stiva;
ctc(a,c,stiva,n);
fflush(stdin);
getchar();
return 0;
}