Pagini recente » Cod sursa (job #2607752) | Cod sursa (job #447665) | Cod sursa (job #263628) | Cod sursa (job #1168243) | Cod sursa (job #2677220)
#include <fstream>
#include <vector>
#include <stack>
#define dim 100010
using namespace std;
vector<int> a[dim];
vector<int> sol[dim];
stack<int> s;
int f[dim];
int niv[dim];
int low[dim];
int is[dim];
int i,n,m,u,g,x,y;
void dfs (int nod) {
g++;
niv[nod]=g;
low[nod]=g;
f[nod]=1;
is[nod]=1;
s.push(nod);///stiva in care punem nodurile parcurse deja
is[nod]=1;///nodul se afla in stiva
for (auto vecin:a[nod]) {
if (f[vecin]==0) {
dfs(vecin);
low[nod]=min(low[nod],low[vecin]);
}
else if (is[vecin]){
low[nod]=min(low[nod],low[vecin]);
}
}
///noddurile ce se afla in acceasi componenta conexa ar trebui sa aiba acelasi low
if (low[nod]==niv[nod]) {
u++;
while (s.top()!=nod) {
sol[u].push_back(s.top());
s.pop();
}
sol[u].push_back(s.top());
s.pop();
}
}
int main() {
ifstream fin("ctc.in");
ofstream fout("ctc.out");
fin>>n>>m;
for (i=1;i<=m;i++) {
fin>>x>>y;
a[x].push_back(y);
}
for (i=1;i<=n;i++) {
if (f[i]==0) {
dfs(i);
}
}
fout<<u<<"\n";
for (i=1;i<=u;i++) {
for (auto nod:sol[i]) {
fout<<nod<<" ";
}
fout<<"\n";
}
return 0;
}