Pagini recente » Cod sursa (job #2620279) | Cod sursa (job #1705375) | Cod sursa (job #1829762) | Cod sursa (job #2757715) | Cod sursa (job #1861468)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int a[10001][10001], at[10001][10001],n, m, viz[10001], nrcc, k, v[10001];
void citire()
{
f>>n>>m;
int i, x, y;
for (i = 1; i <= m; i++)
{
f>>x>>y;a[x][y] = at[y][x] = 1;
}
}
void DFS1(int nod) //parcurgerea in adancime
{
viz[nod] = 1;
for (int i = 1; i <= n; i++)
if (!viz[i] && a[nod][i]) DFS1(i);
}
void DFS2(int nod) //parcurgerea in adancime
{
viz[nod] = 1;
for (int i = 1; i <= n; i++)
if (!viz[i] && a[nod][i]) DFS2(i);
g<<nod<<' ';
}
void DFS_transp(int nod) //parcurgerea in adancime
{
viz[nod] = 1;
for (int i = 1; i <= n; i++)
if (!viz[i] && at[nod][i]) DFS_transp(i);
v[++k]=nod;
}
int main()
{
citire();int i;
//cautarea in adancime pe graful transpus
for(i=1;i<=n;i++)
if(!viz[i]) DFS_transp(i);
//resetare vector viz
for(i=1;i<=n;i++) viz[i]=0;
//parcurgerea in adancime pe graful initial si numarare componente
for(i=n;i>=1;i--)
if(!viz[i])
{nrcc++;DFS1(v[i]);}
g<<nrcc<<'\n';
//parcurgerea in adancime pe graful initial si afisare componente
for(i=1;i<=n;i++) viz[i]=0;
for(i=n;i>=1;i--)
if(!viz[i])
{
DFS2(v[i]);g<<'\n';
}
f.close();g.close();return 0;
}