Pagini recente » Cod sursa (job #2741881) | Cod sursa (job #1249651) | Cod sursa (job #577144) | Cod sursa (job #437140) | Cod sursa (job #1250482)
#include <fstream>
#define NMAX 101
using namespace std;
ofstream fout ("ctc.out");
char uz[NMAX];
int A[NMAX][NMAX], AT[NMAX][NMAX];
char v1[NMAX], v2[NMAX];
int n, m;
void citire(); void DFS(int, char[], int A[NMAX][NMAX]); void rez();
int main()
{
citire();
rez();
return 0;
}
void citire()
{
ifstream fin ("ctc.in");
fin>>n>>m;
int i, x, y;
for (i=1; i<=m; ++i)
{
fin>>x>>y;
//am arc de la x la y
A[x][++A[x][0]]=y;
//in graful transpus, am arc de la y la x
AT[y][++AT[y][0]]=x;
}
fin.close();
return;
}
void rez()
{
//DFS pentru graful initial
//DFS pentru graful transpus
int i, j;
for (i=1; i<=n; ++i)
if (!uz[i])
{
DFS (i, v1, A);
DFS (i, v2, AT);
//afisez componenta conexa
for (j=1; j<=n; ++j)
{
if (v1[j] && v2[j])
{
fout<<j<<" ";
uz[j]=1;//se afla intr-o componenta conexa
}
v1[j]=v2[j]=0;
}
fout<<"\n";
}
fout.close();
return;
}
void DFS (int vf, char v[], int A[NMAX][NMAX])
{
int i;
v[vf]=1;//acest varf este accesibil
for (i=1; i<=A[vf][0]; ++i)
if (!v[A[vf][i]])
DFS (A[vf][i], v, A);
return;
}