Pagini recente » Cod sursa (job #2565211) | Cod sursa (job #2264863) | Cod sursa (job #441290) | Cod sursa (job #2300098) | Cod sursa (job #2794668)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int N = 1e5 + 1;
int n, m, x, y, cnt, indecs;
vector<int> c[N], comp[N];
stack<int> s;
struct varf{
int ind = -1, lowlink;
bool peStiva = 0;
}v[N];
void tarzan(int nod){
v[nod].ind = v[nod].lowlink = indecs;
s.push(nod);
v[nod].peStiva = 1;
indecs++;
for(int y: c[nod]){
if(v[y].ind == -1){
tarzan(y);
v[nod].lowlink = min(v[nod].lowlink, v[y].lowlink);
}else if(v[y].peStiva)
v[nod].lowlink = min(v[nod].lowlink, v[y].ind); // teoretic asa e corect, dar merge si v[y].lowlink
}
if(v[nod].ind == v[nod].lowlink){
cnt++;
int w;
do{
w = s.top();
comp[cnt].push_back(w);
v[w].peStiva = 0;
s.pop();
}while(w != nod);
}
}
int main(){
f >> n >> m;
for(int i = 0; i < m; i++){
f >> x >> y;
c[x].push_back(y);
}
f.close();
for(int i = 1; i <= n; i++){
if(v[i].ind == -1)
tarzan(i);
}
g << cnt << '\n';
for(int i = 1; i <= cnt; i++){
for(int nod: comp[i])
cout << nod << ' ';
g << '\n';
}
g.close();
}