Pagini recente » Cod sursa (job #263783) | Cod sursa (job #2766757) | Cod sursa (job #2714780) | Cod sursa (job #746925) | Cod sursa (job #2312932)
#include <fstream>
#include <vector>
#include <stack>
#define input "ctc.in"
#define output "ctc.out"
#define NMAX 100005
using namespace std;
ifstream in(input);
ofstream out(output);
vector < int > muchii[NMAX], muchii_gt[NMAX], componente[NMAX];
stack < int > postpone;
int noduri, muchi, ctc, uz[NMAX];
void Read_Data()
{
in >> noduri >> muchi;
for (int i = 1; i <= muchi; i++)
{
int x, y;
in >> x >> y;
muchii[x].push_back(y);
muchii_gt[y].push_back(x);
}
}
void DFS_original(int nod)
{
uz[nod] = 1;
for (unsigned i = 0; i < muchii[nod].size(); i++)
{
int new_nod = muchii[nod][i];
if (!uz[new_nod]) DFS_original(new_nod);
}
postpone.push(nod);
}
void DFS_made_in_china(int nod)
{
componente[ctc].push_back(nod);
uz[nod] = 0;
for (unsigned i = 0; i < muchii_gt[nod].size(); i++)
{
int new_nod = muchii_gt[nod][i];
if (uz[new_nod]) DFS_made_in_china(new_nod);
}
}
void Solve_Cerinta_Jupanului()
{
// Parcurgem graful in adancime
for (int i = 1; i <= noduri; i++)
if (!uz[i]) DFS_original(i);
// Determinam componentele conexe pe mafii
while (!postpone.empty())
{
int nod = postpone.top();
if (uz[nod])
{
ctc++;
DFS_made_in_china(nod);
}
postpone.pop();
}
// Afisam capului di tuti capi ce am aflat
out << ctc << "\n";
for (int i = 1; i <= ctc; i++)
{
for (unsigned j = 0; j < componente[i].size(); j++)
out << componente[i][j] << " ";
out << "\n";
}
}
int main()
{
Read_Data();
Solve_Cerinta_Jupanului();
return 0;
}