Pagini recente » Cod sursa (job #476536) | Cod sursa (job #1210912) | Cod sursa (job #1710055) | Cod sursa (job #1001685) | Cod sursa (job #520596)
Cod sursa(job #520596)
#include <fstream>
#include <vector>
#define MAXN 100010
using namespace std;
int n,m,vizitat[MAXN],final[MAXN],ordine[MAXN],timp,nr,ap[MAXN];
vector <int> graf[MAXN],graft[MAXN];
struct solutie{
int nod, comp;
} sol[MAXN];
bool cmp(solutie a, solutie b)
{
if(a.comp>b.comp)
return 0;
else
if(a.comp<b.comp)
return 1;
else
if(a.comp==b.comp)
if(a.nod>b.nod)
return 0;
else
return 1;
}
void df_final(int nod)
{
int i;
vizitat[nod]=1;
for(i=0;i<graf[nod].size();i++)
if(!vizitat[graf[nod][i]])
df_final(graf[nod][i]);
timp++;
final[nod]=timp;
}
void stabilire_ordine()
{
int i,k;
for(i=1;i<=n;i++)
{
k=final[i];
ordine[n-k+1]=i;
}
}
void df(int nod)
{
int i;
for(i=0;i<graft[nod].size();i++)
if(!vizitat[graft[nod][i]])
{
vizitat[graft[nod][i]]=1;
sol[graft[nod][i]].nod=graft[nod][i];
sol[graft[nod][i]].comp=nr;
df(graft[nod][i]);
}
}
int main()
{
int i,x,y,k;
ifstream f("ctc.in");
ofstream g("ctc.out");
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
graf[x].push_back(y);
graft[y].push_back(x);
}
df_final(1);
stabilire_ordine();
for(i=1;i<=n;i++)
vizitat[i]=0;
for(i=1;i<=n;i++)
{
k=ordine[i];
if(!vizitat[k])
{
nr++;
vizitat[k]=1;
sol[k].nod=k;
sol[k].comp=nr;
df(k);
}
}
sort(sol+1,sol+n+1,cmp);
g<<nr<<"\n";
g<<sol[1].nod<<" ";
for(i=2;i<=n;i++)
{
if(sol[i].comp>sol[i-1].comp)
g<<"\n";
g<<sol[i].nod<<" ";
}
g<<"\n";
return 0;
}