Pagini recente » Cod sursa (job #1534013) | Cod sursa (job #2652272) | Cod sursa (job #2680827) | Cod sursa (job #3168969) | Cod sursa (job #3207520)
#include <fstream>
#include <algorithm>
#include <vector>
#define NMAX 100000
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
struct type_node{
int d, l;
vector<int>edge;
}graf[NMAX + 1];
int globalTime, nrComp;
vector<int>comp[NMAX + 1];
int stiva[NMAX + 1], k;
void dfs(int nod) {
int momStiva = k;
k++;
stiva[k] = nod;
globalTime++;
graf[nod].d = graf[nod].l = globalTime;
for(auto copil : graf[nod].edge) {
if(graf[copil].d == 0) {
dfs(copil);
}
graf[nod].l = min(graf[nod].l, graf[copil].l);
}
if(graf[nod].l == graf[nod].d) {
nrComp++;
while(stiva[k] != nod) {
comp[nrComp].push_back(stiva[k--]);
}
comp[nrComp].push_back(stiva[k--]);
}
}
signed main() {
int n, m, a, b;
cin>>n>>m;
while(m--) {
cin>>a>>b;
graf[a].edge.push_back(b);
}
for(int i = 1; i <= n; i++) {
if(graf[i].d == 0)
dfs(i);
}
cout<<nrComp<<"\n";
while(nrComp--) {
for(auto nod : comp[nrComp + 1]){
cout<<nod<<" ";
}
cout<<"\n";
}
return 0;
}