Pagini recente » Cod sursa (job #543566) | Cod sursa (job #1681418) | Cod sursa (job #551764) | Cod sursa (job #183834) | Cod sursa (job #2797060)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define N 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int viz[N], viz_t[N];
stack <int> S;
vector <int> c[N];
class Graph {
public:
int n; //nr de varfuri
int m; //nr de muchii
vector <int> a[N];
vector <int> a_t[N];
Graph(int n, int m)
{
this->n = n;
this->m = m;
}
void Citire_orientat()
{
int i;
int x, y;
for (i = 0; i < m; i++)
{
fin >> x >> y;
a[x].push_back(y);
a_t[y].push_back(x);
}
}
void DFS(int x);
void DFS_T(int x, int ct);
void CompTConexe();
void ParcurgereGraf();
};
void Graph::ParcurgereGraf()
{
int i;
for (i = 1; i <= n; i++)
if (!viz[i])
DFS(i);
}
void Graph::DFS(int x)
{
int i;
viz[x] = 1;
for (i = 0; i < a[x].size(); i++)
if (!viz[a[x][i]])
DFS(a[x][i]);
S.push(x);
}
void Graph::DFS_T(int x,int ct)
{
int i;
viz_t[x] = 1;
c[ct].push_back(x); //pt fiecare nod, din ce comp tconexa face parte
for (i = 0; i < a_t[x].size(); i++)
if (viz_t[a_t[x][i]] == 0)
DFS_T(a_t[x][i], ct);
}
void Graph::CompTConexe()
{
int i, j, x, ct = 0;
while (!S.empty())
{
x = S.top();
S.pop();
if (viz_t[x] == 0)
{
ct++;
DFS_T(x, ct);
}
}
fout << ct << "\n";
for (i = 1; i <= ct; i++)
{
for (j = 0; j < c[i].size(); j++)
fout << c[i][j] << " ";
fout << "\n";
}
}
int main()
{
int n, m;
fin >> n >> m;
Graph g(n, m);
g.Citire_orientat();
g.ParcurgereGraf();
g.CompTConexe();
return 0;
}