Pagini recente » Cod sursa (job #2286427) | Cod sursa (job #443464) | Cod sursa (job #1645779) | Cod sursa (job #1979809) | Cod sursa (job #1249930)
#include <fstream>
#define NMAX 100001
using namespace std;
ofstream fout ("ctc.out");
char uz[NMAX];
char v1[NMAX], v2[NMAX];
int n, m, nr_ctc;
struct nod
{int inf;
struct nod *urm;
};
typedef struct nod *Lista;
Lista A[NMAX], AT[NMAX], CTC[NMAX];
void inserare(Lista&, Lista, int);
void citire(); void DFS(int, char[], int); 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
inserare (A[x], NULL, y);
//in graful transpus, am arc de la y la x
inserare (AT[y], NULL, x);
}
fin.close();
return;
}
void rez()
{
//DFS pentru graful initial
//DFS pentru graful transpus
int i, j;
Lista q;
for (i=1; i<=n; ++i)
if (!uz[i])
{
++nr_ctc;
DFS (i, v1, 0);
DFS (i, v2, 1);
for (j=1; j<=n; ++j)
{
if (v1[j] && v2[j])
{
inserare(CTC[nr_ctc], NULL, j);
uz[j]=nr_ctc;//se afla intr-o componenta conexa
}
v1[j]=v2[j]=0;
}
}
//afisez componentele tare conexe
fout<<nr_ctc<<"\n";
/*for (i=1; i<=nr_ctc; ++i)
{
for (j=1; j<=n; ++j)
if (uz[j]==i)
fout<<j<<" ";
fout<<"\n";
}*/
for (i=1; i<=nr_ctc; ++i)
{
for (q=CTC[i]; q; q=q->urm)
fout<<q->inf<<" ";
fout<<"\n";
}
fout.close();
return;
}
void DFS (int vf, char v[], int care)
{
Lista q;
v[vf]=1;//acest varf este accesibil
if (!care) q=A[vf];
else q=AT[vf];
for ( ; q; q=q->urm)
if (!v[q->inf])
DFS (q->inf, v, care);
return;
}
void inserare (Lista &prim, Lista p, int x)
{
Lista q;
q=new nod;
q->inf=x;
if (p)
{
q->urm=p->urm;
p->urm=q;
}
else
{
q->urm=prim;
prim=q;
}
return;
}