Pagini recente » Cod sursa (job #2805375) | Cod sursa (job #985659) | Cod sursa (job #380831) | Cod sursa (job #1177631) | Cod sursa (job #2927900)
#include <bits/stdc++.h>
#define NMAX 100000
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
vector <int> vsons[NMAX + 1];
bool is_visited[NMAX + 1];
bool found_component[NMAX + 1];
int vhighestnode[NMAX + 1];
int vlevel[NMAX + 1];
int nctc;
vector <int> vctc[NMAX + 1];
stack <int> stack_ctc;
int index_node;
void dfs(int node, int tata) {
int nsons, i;
nsons = vsons[node].size();
vhighestnode[node] = index_node;
vlevel[node] = index_node;
index_node++;
is_visited[node] = true;
stack_ctc.push(node);
for (i = 0; i < nsons; i++) {
int newnode = vsons[node][i];
if (is_visited[newnode]) {
if (!found_component[newnode])
vhighestnode[node] = min(vhighestnode[node], vlevel[newnode]);
}
else {
dfs(newnode, node);
vhighestnode[node] = min(vhighestnode[node], vhighestnode[newnode]);
}
}
if (vhighestnode[node] == vlevel[node]) {
while (stack_ctc.top() != node) {
vctc[nctc].push_back(stack_ctc.top());
found_component[stack_ctc.top()] = true;
stack_ctc.pop();
}
vctc[nctc++].push_back(node);
found_component[node] = true;
stack_ctc.pop();
}
}
int main() {
int n, m, i, j, node1, node2;
fin >> n >> m;
for (i = 0; i < m; i++) {
fin >> node1 >> node2;
vsons[node1].push_back(node2);
}
for (i = 1; i <= n; i++) {
if (!is_visited[i])
dfs(i, 0);
}
fout << nctc << "\n";
for (i = 0; i < nctc; i++) {
for (j = 0; j < vctc[i].size(); j++)
fout << vctc[i][j] << " ";
fout << "\n";
}
return 0;
}