Pagini recente » Cod sursa (job #3195540) | Monitorul de evaluare | Cod sursa (job #2428764) | Cod sursa (job #1259945) | Cod sursa (job #2263090)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define dMAX 100000
using namespace std;
int n, m, lvl, nrTare;
int x, y;
vector<int> graf[dMAX + 2];
vector<int> grafT[dMAX + 2];
pair<int, int> nivel[dMAX + 2];
int plusminus[dMAX + 2];
bool viz[dMAX + 2], vizpm[dMAX + 2];
vector<int> componente[dMAX + 2];
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void DFS_N(int k) {
viz[k] = true;
for (int i = 0; i < graf[k].size(); i++) {
int newV = graf[k][i];
if (!viz[newV]) {
DFS_N(newV);
lvl++;
}
}
nivel[k] = {k, lvl};
}
void DFS_P(int k) {
plusminus[k]++;
vizpm[k] = true;
for (int i = 0; i < graf[k].size(); i++) {
int newV = graf[k][i];
if (!vizpm[newV] && !viz[newV]) {
DFS_P(newV);
}
}
//vizpm[k] = false;
}
void DFS_M(int k) {
plusminus[k]++;
/*if (plusminus[k] == 2) {
viz[k] = true;
componente[nrTare].push_back(k);
}*/
vizpm[k] = true;
for (int i = 0; i < grafT[k].size(); i++) {
int newV = grafT[k][i];
if (!vizpm[newV] && !viz[newV]) {
DFS_M(newV);
}
}
}
bool Compare(pair<int, int> e1, pair<int, int> e2) {
return e1.second < e2.second;
}
int main()
{
int i, j;
fin >> n >> m;
for (i = 1; i <= m; i++) {
fin >> x >> y;
graf[x].push_back(y);
grafT[y].push_back(x);
}
DFS_N(1);
for (i = 1; i <= n; i++) {
viz[i] = false;
}
sort(nivel + 1, nivel + 1 + n, Compare);
for (i = 1; i <= n; i++) {
int pVerif = nivel[i].first;
if (!viz[pVerif]) {
viz[pVerif] = true;
nrTare++;
for (j = 1; j <= n; j++) {
plusminus[j] = 0;
}
DFS_P(pVerif);
for (j = 1; j <= n; j++) vizpm[j] = false;
DFS_M(pVerif);
for (j = 1; j <= n; j++) vizpm[j] = false;
for (j = 1; j <= n; j++) {
if (plusminus[j] == 2) {
viz[j] = true;
componente[nrTare].push_back(j);
}
}
}
}
fout << nrTare << '\n';
for (i = 1; i <= nrTare; i++) {
for (j = 0; j < componente[i].size(); j++) {
fout << componente[i][j] << ' ';
}
fout << '\n';
}
return 0;
}