Pagini recente » Cod sursa (job #2573484) | Cod sursa (job #2780768) | Cod sursa (job #530020) | Cod sursa (job #3001057) | Cod sursa (job #1249911)
#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];
void inserare(Lista&, Lista, int);
void citire(); void DFS(int, char[], Lista *); 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;
for (i=1; i<=n; ++i)
if (!uz[i])
{
++nr_ctc;
DFS (i, v1, A);
DFS (i, v2, AT);
for (j=1; j<=n; ++j)//aici se poate optimiza
{
if (v1[j] && v2[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";
}
fout.close();
return;
}
void DFS (int vf, char v[], Lista *A)
{
Lista q;
v[vf]=1;//acest varf este accesibil
for (q=A[vf]; q; q=q->urm)
if (!v[q->inf])
DFS (q->inf, v, A);
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;
}