Pagini recente » Cod sursa (job #1672557) | Cod sursa (job #1097439) | Cod sursa (job #1672558) | Cod sursa (job #1097268) | Cod sursa (job #3319895)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
const int NMAX = 100000;
int N, M, nrc;
vector<int> G[NMAX+1], CTC[NMAX+1];
int D[NMAX+1], Dmin[NMAX+1], Timp = 0;
stack<int> S;
bool inSt[NMAX+1];
void citire() {
int x, y;
f >> N >> M;
for (int i=1; i<=M; i++) {
f >> x >> y;
G[x].push_back(y);
}
}
void DFS(int x) {
D[x] = ++Timp;
Dmin[x] = D[x];
S.push(x);
inSt[x] = 1;
//
for (const auto &y : G[x]) {
if(D[y] == 0) {
DFS(y);
Dmin[x] = min(Dmin[x], Dmin[y]);
} else {
if (inSt[y] == 1)
Dmin[x] = min(Dmin[x], D[y]);
}
}
//
if (Dmin[x] == D[x]) {
int u;
nrc++;
do {
u = S.top();
CTC[nrc].push_back(u);
S.pop();
inSt[u] = 0;
} while(x != u);
}
}
void afisare() {
g << nrc << '\n';
for (int i=1; i<=nrc; i++) {
for (const auto &x : CTC[i])
g << x << ' ';
g << '\n';
}
}
int main(){
citire();
//
for (int i=1; i<=N; i++)
if(D[i] == 0)
DFS(i);
//
afisare();
f.close();
g.close();
return 0;
}