Pagini recente » Cod sursa (job #722653) | Cod sursa (job #2881517) | Cod sursa (job #1597329) | Cod sursa (job #2152485) | Cod sursa (job #2758078)
#include <iostream>
#include <fstream>
using namespace std;
int n, m, componenta[100001], nr;
bool vizitat_exterior[100001], vizitat_interior[100001];
struct Node
{
int data;
Node *next;
}*vecini[100001];
void Adaugare(int nod, int destinatie)
{
Node *p = new Node;
p->data = nod;
p->next = vecini[destinatie];
vecini[destinatie] = p;
}
void Citire()
{
ifstream f("ctc.in");
int nod1, nod2;
f >> n >> m;
for(int i = 0; i < m; i++)
{
f >> nod1 >> nod2;
Adaugare(nod1, nod2);
}
}
void DfsExterior(int varf)
{
vizitat_exterior[varf] = true;
for(Node *p = vecini[varf]; p != NULL; p = p->next)
if(!vizitat_exterior[p->data])
DfsExterior(p->data);
}
void DfsInterior(int varf)
{
vizitat_interior[varf] = true;
for(int i = 1; i <= n; i++)
if(!vizitat_interior[i])
{
for(Node *p = vecini[i]; p != NULL; p = p->next)
if(p->data == varf)
DfsInterior(i);
}
}
void ResetareViz()
{
for(int i = 1; i <= n; i++)
{
vizitat_exterior[i] = false;
vizitat_interior[i] = false;
}
}
void GasireNoduri()
{
for(int i = 1; i <= n; i++)
if(vizitat_interior[i] && vizitat_exterior[i])
componenta[i] = nr;
}
void DeterminareComponenteTareConexe()
{
for(int i = 1; i <= n; i++)
if(!componenta[i])
{
nr++;
ResetareViz();
DfsExterior(i);
DfsInterior(i);
GasireNoduri();
}
}
void Afisare()
{
ofstream g("ctc.out");
g << nr << '\n';
for(int i = 1; i <= nr; i++)
{
for(int j = 1; j <= n; j++)
if(componenta[j] == i)
g << j << ' ';
g << '\n';
}
}
int main()
{
Citire();
DeterminareComponenteTareConexe();
Afisare();
return 0;
}