Pagini recente » Cod sursa (job #1545300) | Cod sursa (job #941035) | Cod sursa (job #450837) | Cod sursa (job #407455) | Cod sursa (job #3269804)
#include <bits/stdc++.h>
std::ifstream fin("test.in");
std::ofstream fout("test.out");
int n, m;
std::vector<std::vector<int>> nums;
std::vector<int> minim;
std::vector<int> viz;
std::vector<int> inStack;
std::stack<int> s;
std::vector<std::vector<int>> rez;
int i = 0;
void scc(int node)
{
viz[node] = minim[node] = i;
i++;
s.push(node), inStack[node] = 1;
for(int x : nums[node])
{
if(viz[x] == -1)
{
scc(x);
minim[node] = std::min(minim[node], minim[x]);
}
else if(inStack[x])
{
minim[node] = std::min(minim[node], minim[x]);
}
}
if(minim[node] == viz[node])
{
std::vector<int> st;
int sccCurent;
do
{
st.push_back(sccCurent = s.top());
s.pop(), inStack[sccCurent] = 0;
}while(sccCurent != node);
rez.push_back({});
for(auto it = st.begin(); it != st.end(); it++)
{
rez.back().push_back(*it);
}
}
}
int main()
{
fin >> n >> m;
nums.resize(n + 1, std::vector<int>(0));
viz.resize(n + 1 , -1);
inStack.resize(n + 1);
minim.resize(n + 1);
for(int i = 1; i <= m; i++)
{
int x, y;
fin >> x >> y;
nums[x].push_back(y);
}
for(int i = 1; i <= n; i++)
{
std::sort(nums[i].begin(), nums[i].end());
}
for(int i = 1; i <= n; i++)
{
if(viz[i] == -1)
{
scc(1);
}
}
fout << rez.size() << '\n';
for(auto x : rez)
{
for(int y : x)
{
fout << y << ' ';
}
fout << '\n';
}
}