Pagini recente » Cod sursa (job #2643476) | Cod sursa (job #2122938) | Cod sursa (job #760937) | Cod sursa (job #3151290) | Cod sursa (job #2929036)
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<int> adj[100001], componente[100001];
int ids[100001], low[100001];
stack<int> stiva;
bool peStiva[100001];
int id = 1;
int ctc = 0;
void dfs(int nod_curent){
stiva.push(nod_curent);
peStiva[nod_curent] = true;
ids[nod_curent] = low[nod_curent] = id++;
for(int i = 0; i < adj[nod_curent].size(); i++){
int vecin = adj[nod_curent][i];
if(ids[vecin] == 0)
dfs(vecin);
if(peStiva[vecin] == true)
low[nod_curent] = min(low[nod_curent], low[vecin]);
}
if(ids[nod_curent] == low[nod_curent]){
int nod;
ctc++;
do{
nod = stiva.top();
low[nod] = ids[nod_curent];
peStiva[nod] = false;
stiva.pop();
componente[ctc].push_back(nod);
} while(nod != nod_curent);
}
}
int main()
{
int n, m, x, y;
in >> n >> m;
for(int i = 0; i < m; i++){
in >> x >> y;
adj[x].push_back(y);
}
for(int i = 1; i <= n; i++){
if(ids[i] == 0)
dfs(i);
}
out << ctc <<"\n";
for(int i = 1; i <= ctc; i++){
for(int j = 0; j < componente[i].size(); j++)
out << componente[i][j]<<" ";
out <<"\n";
}
return 0;
}