Pagini recente » Cod sursa (job #40449) | Cod sursa (job #2785097) | Runda 3 preONI 2007 | Ecuatie | Cod sursa (job #3297552)
#include <bits/stdc++.h>
#define NMAX 100000
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, a, b;
int nr_cmp_tari;
vector<int> gr[NMAX + 2], tr[NMAX + 2];
vector<bool> viz(NMAX + 2), viz_2(NMAX + 2);
stack<int> st;
vector<vector<int>> cmp_tari_cnx;
void DFS(int nod) {
viz[nod] = 1;
for (int vec : gr[nod]) {
if (!viz[vec]) {
DFS(vec);
}
}
st.push(nod);
}
void DFS_2(int nod) {
viz_2[nod] = 1;
cmp_tari_cnx[nr_cmp_tari].emplace_back(nod);
for (int vec : tr[nod]) {
if (!viz_2[vec]) {
DFS_2(vec);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
fin.tie(NULL);
fout.tie(NULL);
fin >> n >> m;
while (m--) {
fin >> a >> b;
gr[a].emplace_back(b);
tr[b].emplace_back(a);
}
for (int i = 1; i <= n; i++) {
if (!viz[i]) {
DFS(i);
}
}
while (!st.empty()) {
int nod_cr = st.top();
st.pop();
if (!viz_2[nod_cr]) {
cmp_tari_cnx.push_back(vector<int>(0));
DFS_2(nod_cr);
nr_cmp_tari++;
}
}
fout << nr_cmp_tari << '\n';
for (int i = 0; i < nr_cmp_tari; i++) {
for (int j = 0; j < cmp_tari_cnx[i].size(); j++) {
fout << cmp_tari_cnx[i][j] << ' ';
}
fout << '\n';
}
return 0;
}