Pagini recente » Cod sursa (job #309545) | Cod sursa (job #2947292) | Cod sursa (job #755169) | Cod sursa (job #24347) | Cod sursa (job #2785737)
#include <bits/stdc++.h>
#define NMAX 100009
#define IN_FILE "ctc.in"
#define OUT_FILE "ctc.out"
using namespace std;
stack<int> S;
vector<int> g[NMAX];
vector<int> components[NMAX];
int no_components;
int index_value;
int ind[NMAX], lnk[NMAX];
bool on_stack[NMAX];
void tarjan(int k);
int main()
{
int n, m;
FILE *fd_in = fopen(IN_FILE, "r");
FILE *fd_out = fopen(OUT_FILE, "w");
fscanf(fd_in, "%d %d", &n, &m);
for (int i = 0; i < m; i++)
{
int x, y;
fscanf(fd_in, "%d %d", &x, &y);
g[x].push_back(y);
}
for (int i = 1; i <= n; i++)
{
if (!ind[i])
tarjan(i);
}
fprintf(fd_out, "%d\n", no_components);
for (int i = 0; i < no_components; i++)
{
for (auto component_element : components[i])
{
fprintf(fd_out, "%d ", component_element);
}
fprintf(fd_out, "\n");
}
return 0;
}
void tarjan(int node_index_value)
{
index_value++;
ind[node_index_value] = index_value;
lnk[node_index_value] = index_value;
S.push(node_index_value);
on_stack[node_index_value] = true;
for (auto ngb_index_value : g[node_index_value])
{
if (!ind[ngb_index_value])
{
tarjan(ngb_index_value);
lnk[node_index_value] = min(lnk[node_index_value], lnk[ngb_index_value]);
}
else if (on_stack[ngb_index_value])
{
lnk[node_index_value] = min(lnk[node_index_value], ind[ngb_index_value]);
}
}
if (lnk[node_index_value] == ind[node_index_value])
{
int stack_elem;
do
{
stack_elem = S.top();
S.pop();
// on_stack[stack_elem] = false;
components[no_components].push_back(stack_elem);
} while (stack_elem != node_index_value);
no_components++;
}
}