Pagini recente » Monitorul de evaluare | Istoria paginii utilizator/rjytyjtjtj | Monitorul de evaluare | Cod sursa (job #1471856) | Cod sursa (job #1963445)
#include <iostream>
#include <cstdio>
#include <list>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
typedef pair<int, int> Pair;
#define G 0 //graf initial
#define T 1 //graf transpus
int n, m, nrsol;
vector<int> culoare;
vector<list<int>> graf[2];
vector<int> sortareVector;
vector<vector<int>> solutiones;
stack<int> stiva;
void read() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int n1, n2;
cin >> n >> m;
culoare.resize(n);
graf[G].resize(n);
graf[T].resize(n);
sortareVector.resize(n);
for(int i = 0; i < m; ++i) {
scanf("%d%d", &n1, &n2);
graf[G][n1 - 1].push_back(n2 - 1); //graf
graf[T][n2 - 1].push_back(n1 - 1); //graf transpus
}
}
void DFS(int nod, bool TR);
void Kosaraju() {
bool continua = true;
while (continua) {
int nod = 0;
while (nod < n && culoare[nod]) {
++nod;
}
if (nod == n) {
continua = false;
continue;
}
DFS(nod, G);
}
culoare = vector<int>(n);
while(!stiva.empty()) {
int nod = stiva.top();
stiva.pop();
if (!culoare[nod]) {
solutiones.push_back(vector<int>());
DFS(nod, T);
nrsol++;
}
}
}
void DFS(int nod, bool TR) {
culoare[nod] = 1;
for (auto vecin : graf[TR][nod]) {
if (!culoare[vecin]) {
DFS(vecin, TR);
}
}
culoare[nod] = 2;
if (TR == G) {
stiva.push(nod);
} else {
solutiones[nrsol].push_back(nod + 1);
}
}
void write() {
printf("%d\n", nrsol);
for(int i = 0; i < nrsol; ++i) {
for (auto x : solutiones[i]) {
printf("%d ", x);
}
printf("\n");
}
}
int main()
{
read();
Kosaraju();
write();
// for (int nod = 0; nod < n; ++nod) {
// for (auto vecin : noduri[nod]) {
// cout << vecin << " ";
// }
// cout << endl;
// }
//
// for (int nod = 0; nod < n; ++nod) {
// cout << "nod: " << nod + 1 << " culoare: "
// << culoare[nod] << " timpi: " << timpi[nod].first
// << " " << timpi[nod].second << endl;
// }
// int nod = 0;
// while (!stiva.empty()) {
// sortareVector[nod++] = stiva.top();
// stiva.pop();
// }
// cout << endl << "Sortare: ";
// for (int nod = 0; nod < n; ++nod) {
// cout << sortareVector[nod] + 1 <<" ";
// }
return 0;
}