Pagini recente » Cod sursa (job #580103) | Cod sursa (job #1334272) | Cod sursa (job #624243) | Cod sursa (job #1819501) | Cod sursa (job #2925505)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int id = 1, num_scc = 0;
vector<vector<int>> sccs;
void dfs(int curr_node, int& n, vector<vector<int>>&ad_list, int low_vals[100001], int ids[100001], bool on_stack[100001], stack<int>& scc_stack)
{
scc_stack.push(curr_node);
on_stack[curr_node] = true;
ids[curr_node] = low_vals[curr_node] = id;
id++;
for(auto it = ad_list[curr_node].begin(); it < ad_list[curr_node].end(); it++)
{
if(ids[*it] == 0)
{
dfs(*it, n, ad_list, low_vals, ids, on_stack, scc_stack);
low_vals[curr_node] = min(low_vals[curr_node], low_vals[*it]);
}
else if(on_stack[*it])
low_vals[curr_node] = min(low_vals[curr_node], low_vals[*it]);
}
if(ids[curr_node] == low_vals[curr_node])
{
num_scc++;
vector<int> scc;
while(curr_node != scc_stack.top())
{
int node = scc_stack.top();
on_stack[node] = false;
low_vals[node] = ids[curr_node];
scc.push_back(node);
scc_stack.pop();
}while(curr_node != scc_stack.top());
int node = scc_stack.top();
on_stack[node] = false;
low_vals[node] = ids[curr_node];
scc.push_back(node);
scc_stack.pop();
sccs.push_back(scc);
}
}
int main()
{
int n, m;
int low_vals[100001];
int ids[100001];
bool on_stack[100001];
stack<int> scc_stack;
fin >> n >> m;
vector<vector<int>>ad_list(n+1);
for(int i = 1; i <= m; i++)
{
int x, y;
fin >> x >> y;
ad_list[x].push_back(y);
}
for(int i = 1; i <= n; i++)
if(ids[i] == 0)
dfs(i, n, ad_list, low_vals, ids, on_stack, scc_stack);
fout << num_scc << '\n';
for(int i = 0; i < num_scc; i++)
{
for(auto j = sccs[i].begin(); j < sccs[i].end(); j++)
fout << *j << " ";
fout << '\n';
}
}