Pagini recente » Cod sursa (job #2177378) | Cod sursa (job #2536102) | Cod sursa (job #1968522) | Cod sursa (job #2739602) | Cod sursa (job #2121267)
#include<fstream>
#include<vector>
using namespace std;
ifstream in ("ctc.in");
ofstream out ("ctc.out");
bool hz[100001],in_stiva[100001];
int n,m,low[100001],lev[100001],ctc,nr,a,b;
vector<int> v[100001],stiva,componente[100001];
void dfs (int knot) {
stiva.push_back(knot);
hz[knot] = 1;
in_stiva[knot] = 1;
low[knot] = ++nr;
lev[knot] = nr;
for (int i = 0; i < v[knot].size(); i ++) {
int vecin = v[knot][i];
if (hz[vecin] == 0) {
dfs (vecin);
}
if (in_stiva[vecin] == 1) {
if (low[vecin] < low[knot]) {
low[knot] = low[vecin];
}
}
}
if (lev[knot] == low[knot]) {
ctc ++;
while (stiva.size() != 0 && stiva[stiva.size()-1] != knot) {
componente[ctc].push_back ( stiva[stiva.size()-1]);
in_stiva[stiva[stiva.size()-1]] = 0;
stiva.pop_back();
}
componente[ctc].push_back ( stiva[stiva.size()-1]);
in_stiva[stiva[stiva.size()-1]] = 0;
stiva.pop_back();
}
}
int main (void) {
in >> n >> m;
for (int i = 1; i <= m; i ++) {
in >> a >> b;
v[a].push_back (b);
}
nr = 0;
for (int i = 1; i <= n; i ++) {
if (hz[i] == 0) {
dfs (i);
}
}
out << ctc <<"\n";
for (int i = 1; i <= ctc; i ++) {
for (int j = 0; j < componente[i].size(); j ++) {
out <<componente[i][j] <<" ";
}
out <<"\n";
}
return 0;
}