Pagini recente » Cod sursa (job #2202042) | Cod sursa (job #1753358) | Cod sursa (job #1611420) | Cod sursa (job #1325343) | Cod sursa (job #1259741)
//Problem plan from Infoarena
// "We are drowning in information and starved for knowledge."
#include <cassert>
#include <cmath>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define int64 long long
const int inf = 0x3f3f3f3f, kMaxN = 100005;
ifstream in("ctc.in");
ofstream out("ctc.out");
bool viz[kMaxN];
int ord[kMaxN];
vector<int> vertex[kMaxN], vertex_back[kMaxN];
vector<int> ctc_el[kMaxN]; int ctc[kMaxN];
vector<int> ctc_vertex[kMaxN]; int ctc_in[kMaxN];
void df_1(int nod) {
if (viz[nod])
return ;
viz[nod] = true;
ord[++ord[0]] = nod;
for (int it : vertex[nod])
df_1(it);
return ;
}
void df_2 (int nod) {
if (viz[nod])
return ;
viz[nod] = true;
ctc[nod] = ctc[0];
for (int itr : vertex_back[nod])
df_2(itr);
return ;
}
int main() {
int n, m;
in >> n >> m;
for (int i = 1; i <= m; ++i) {
int a, b;
in >> a >> b;
vertex[a].push_back(b);
vertex_back[b].push_back(a);
}
for (int i = 1; i <= n; ++i)
df_1(i);
for (int i = 1; i <= n; ++i)
viz[i] = 0;
for (int i = 1; i <= n; ++i)
if (not viz[ord[i]]) {
++ctc[0];
df_2(ord[i]);
}
for (int i = 1; i <= n; ++i) {
ctc_el[ctc[i]].push_back(i);
for (int it : vertex[i])
if (ctc[i] != ctc[it]) {
ctc_vertex[ctc[i]].push_back(ctc[it]);
ctc_in[ctc[it]]++;
}
}
out << ctc[0] << '\n';
for (int i = 1; i <= int(ctc[0]); ++i, out << '\n')
for (int itr : ctc_el[i])
out << itr << ' ';
return 0;
}