Pagini recente » Cod sursa (job #232771) | Cod sursa (job #2381520) | Cod sursa (job #1025244) | Profil Djok | Cod sursa (job #1550809)
#include <fstream>
#include <vector>
#include <stack>
int n;
std::vector < std::vector < int > > adj_list, components;
std::vector < int > comp, low, in_stack, c;
std::stack < int > st;
int comps;
void tarjan(int u)
{
comp[u] = low[u] = comps++;
st.push(u);
in_stack[u] = 1;
std::size_t i;
for(i = 0 ; i < adj_list[u].size() ; ++i)
{
int v = adj_list[u][i];
if(comp[v] == -1)
{
tarjan(v);
low[u] = std::min(low[u], low[v]);
}
else if(in_stack[v])
{
low[u] = std::min(low[u], low[v]);
}
}
if(comp[u] == low[u])
{
c.clear();
int node;
while(node != u)
{
node = st.top();
st.pop();
c.push_back(node);
in_stack[node] = 0;
}
components.push_back(c);
}
}
int main()
{
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
fin >> n;
adj_list.assign(n + 1, std::vector < int >());
comp.assign(n + 1, -1);
low.assign(n + 1, 0);
in_stack.assign(n + 1, 0);
int m;
fin >> m;
int node_a, node_b;
for(int i = 1 ; i <= m ; ++i)
{
fin >> node_a >> node_b;
adj_list[node_a].push_back(node_b);
}
for(int i = 1 ; i <= n ; ++i)
if(comp[i] == -1)
tarjan(i);
fout << components.size() << "\n";
for(std::size_t i = 0 ; i < components.size() ; ++i)
{
for(std::size_t j = 0 ; j < components[i].size() ; ++j)
fout << components[i][j] << " ";
fout << "\n";
}
return 0;
}