Pagini recente » Cod sursa (job #1945113) | Cod sursa (job #300114) | Cod sursa (job #2239405) | Cod sursa (job #1795334) | Cod sursa (job #3228563)
#include <bits/stdc++.h>
using namespace std;
vector <int> G[100001], T[100001];
stack<int> st;
bitset<100001> viz;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
void DFS1(int nod)
{
viz[nod] = 1;
for (auto& next : G[nod])
if (!viz[next])
DFS1(next);
st.push(nod);
}
vector<vector<int> > ctc;
void DFS2(int nod)
{
viz[nod] = 1;
ctc.back().push_back(nod);
for (auto next : T[nod])
if (!viz[next])
DFS2(next);
}
int main() {
int n, m;
fin >> n >> m;
while (m--) {
int x, y;
fin >> x >> y;
G[x].push_back(y);
T[y].push_back(x);
}
for (int i = 1; i <= n; i++)
if (!viz[i])
DFS1(i);
viz.reset();
while (!st.empty()) {
if (!viz[st.top()]) {
ctc.push_back({});
DFS2(st.top());
}
st.pop();
}
fout << ctc.size() << "\n";
for (auto &cc: ctc)
{
for (auto& el : cc)
fout << el << " ";
fout << "\n";
}
return 0;
}