Pagini recente » Cod sursa (job #2160248) | Cod sursa (job #1512927) | Cod sursa (job #1535234) | Cod sursa (job #1104264) | Cod sursa (job #3269114)
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
fstream fi ("ctc.in", ios::in);
fstream fo ("ctc.out", ios::out);
vector<bool> visited;
vector<forward_list<int>> branches, tbranches;
stack<int> nodes;
int n, m;
int nrOfComponents;
list<list<int>> components;
void read();
void dfs(int, vector<bool> &, vector<forward_list<int>> &, stack<int> &);
void ccc(vector<bool> &, vector<forward_list<int>> &, stack<int> &, list<list<int>> &);
void dfst(int, vector<bool> &, vector<forward_list<int>> &, list<list<int>> &);
void print();
int main() {
read();
dfs(1, visited, branches, nodes);
ccc(visited, tbranches, nodes, components);
print();
return 0;
}
void read() {
int n1, n2;
fi >> n >> m;
visited.resize(n + 1);
branches.resize(m + 1);
tbranches.resize(m + 1);
for (int i = 0; i < m; ++i) {
fi >> n2 >> n1;
branches[n2].push_front(n1);
tbranches[n1].push_front(n2);
}
}
void dfs(int node, vector<bool> &visited, vector<forward_list<int> > &branches, stack<int> &nodes) {
visited[node] = true;
for (auto i: branches[node]) {
if (!visited[i]) {
dfs(i, visited, branches, nodes);
}
}
nodes.push(node);
}
void dfst(int node, vector<bool> &visited, vector<forward_list<int> > &branches, list<list<int>> &components) {
visited[node] = true;
components.back().push_back(node);
for (auto i: branches[node]) {
if (!visited[i]) {
dfst(i, visited, branches, components);
}
}
}
void ccc(vector<bool> &visited, vector<forward_list<int>> &tbranches, stack<int> &nodes, list<list<int>> &components) {
visited.assign(n + 1, false);
while (!nodes.empty()) {
if(!visited[nodes.top()]) {
++nrOfComponents;
components.push_back({});
dfst(nodes.top(), visited, tbranches, components);
}
nodes.pop();
}
}
void print() {
fo << nrOfComponents << nl;
for (auto& j : components) {
for (auto& i: j) {
fo << i << ' ';
}
fo << nl;
}
}