Pagini recente » Cod sursa (job #700403) | Cod sursa (job #1960907) | Cod sursa (job #918816) | Cod sursa (job #2125801) | Cod sursa (job #3268993)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <bits/stdc++.h>
#define in fin
#define out fout
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> v[100001];
stack<int> s;
int low[100001];
int id[100001];
bool in_stiva[100001];
vector< vector<int> > ctc;
int it = 1;
void dfs(int nod){
if(id[nod] != 0) return;
// cout << "Am ajuns in dfs la : " << nod << '\n';
id[nod] = low[nod] = it;
it++;
s.push(nod);
in_stiva[nod] = 1;
// cout << "Calculam LOW pentru : " << nod << " ( id = " << id[nod] << " )\n";
for(int cop : v[nod]){
if(id[cop] == 0 && !in_stiva[cop]){
// cout << " -- > luam in considerare : " << cop << '\n';
dfs(cop);
low[ nod ] = min(low[nod], low[ cop ]);
}else if(in_stiva[cop]){
low[ nod ] = min(low[nod], low[ cop ]);
}
}
// cout << "LOW pentru : " << nod << " este : " << low[nod] << '\n';
if(low[nod] == id[nod] && in_stiva[nod]){
// cout << "------\n";
vector<int> c;
while(true){
int node = s.top();
// cout << "Scoatem " << node << '\n';
c.push_back( node );
in_stiva[ node ] = 0;
s.pop();
if(node == nod) break;
}
ctc.push_back(c);
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m; in >> n >> m;
for(int i = 0; i < m; i++){
int l, r; in >> l >> r;
v[l].push_back(r);
}
for(int i = 1; i <= n; i++){
if(!in_stiva[i]){
dfs(i);
}
}
out << ctc.size() << '\n';
for(int i = 0; i < ctc.size(); i++){
sort(ctc[i].begin(), ctc[i].end());
for(int j = 0; j < ctc[i].size(); j++) out << ctc[i][j] << " ";
out << '\n';
}
return 0;
}