Pagini recente » Cod sursa (job #508761) | Cod sursa (job #177341) | Cod sursa (job #2893413) | Cod sursa (job #2035280) | Cod sursa (job #2481035)
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMax = 80000;
int n, m;
vector<int> g[NMax + 5];
vector<int> gtr[NMax + 5];
vector<int> ctc[NMax + 5];
int nrctc;
int comp[NMax + 5];
int use[NMax + 5];
void resetUse()
{
for(int i = 1; i <= n; i++)
use[i] = 0;
}
void read()
{
fin >> n >> m;
int x, y;
for (int i = 0; i < m; i++)
{
fin >> x >> y;
g[x].push_back(y);
gtr[y].push_back(x);
}
}
void DFS(int x, vector<int> graf[], int pas)
{
use[x]++;
if(use[x] == 2)
ctc[nrctc].push_back(x);
for (int i = 0; i < graf[x].size(); i++)
{
int vecin = graf[x][i];
if(use[vecin] == pas - 1)
DFS(vecin, graf, pas);
}
}
int main()
{
read();
int k = 1;
for (int i = 1; i <= n; i++)
{
if (comp[i] == 0)
{
nrctc++;
DFS(i, g, 1);
DFS(i, gtr, 2);
for(int i = 1; i <= n; i++)
if(use[i] == 2)
comp[i] = k;
resetUse();
k++;
}
}
fout << nrctc << '\n';
for (int i = 1; i <= nrctc; i++)
{
for(int j = 0; j < ctc[i].size(); j++)
fout << ctc[i][j] << ' ';
fout << '\n';
}
}