Pagini recente » Cod sursa (job #1699624) | Cod sursa (job #944285) | Cod sursa (job #8241) | Rating Zaharia Horia (zaharia_horia) | Cod sursa (job #3286376)
#include <bits/stdc++.h>
#define DIM 100000
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m;
int x,y;
vector<int> L[DIM+5];
int compk = 0;
vector<int> comp[DIM+5];
bool u[DIM+5];
bool in[DIM+5];
int niv[DIM+5];
int nma[DIM+5];
int k = 0;
stack <int> s;
void dfs(int nod){
//cout<<nod<<'\n';
u[nod] = 1;
k++;
niv[nod] = k;
nma[nod] = k;
in[nod] = 1;
s.push(nod);
for(auto vec:L[nod]){
if(!u[vec]){
dfs(vec);
nma[nod] = min(nma[nod],nma[vec]);
}else if(in[vec]){
nma[nod] = min(nma[nod],niv[vec]);
}
}
if(niv[nod] == nma[nod]){
compk++;
while(s.top() != nod){
comp[compk].push_back(s.top());
in[s.top()] = 0;
s.pop();
}
comp[compk].push_back(s.top());
in[s.top()] = 0;
s.pop();
}
}
int main()
{
f>>n>>m;
for(int i=1;i<=m;i++){
f>>x>>y;
L[x].push_back(y);
}
for(int i=1;i<=n;i++){
if(!u[i]){
dfs(i);
}
}
g<<compk<<'\n';
for(int i=1;i<=compk;i++){
for(auto j:comp[i]){
g<<j<<" ";
}
g<<'\n';
}
return 0;
}