Pagini recente » Cod sursa (job #517995) | Cod sursa (job #1007301) | Cod sursa (job #2629538) | Cod sursa (job #2558540) | Cod sursa (job #2785475)
#include <bits/stdc++.h>
#define NMAX 100009
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
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;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
g[x].push_back(y);
}
for (int i = 1; i <= n; i++)
{
if (!ind[i])
tarjan(i);
}
printf("%d\n", no_components);
for (int i = 0; i < no_components; i++)
{
for (auto component_element : components[i])
{
printf("%d ", component_element);
}
printf("\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();
components[no_components].push_back(stack_elem);
} while (stack_elem != node_index_value);
no_components++;
}
}