Pagini recente » Cod sursa (job #3039195) | Cod sursa (job #2529816) | Cod sursa (job #2115184) | Cod sursa (job #2179168) | Cod sursa (job #3269802)
#include <bits/stdc++.h>
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.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::set<int> st;
int sccCurent = s.top(); s.pop();
while(sccCurent != node)
{
st.insert(sccCurent);
inStack[sccCurent] = 0;
sccCurent = s.top(); s.pop();
}
st.insert(sccCurent);
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])
{
scc(1);
}
}
fout << rez.size() << '\n';
for(auto x : rez)
{
for(int y : x)
{
fout << y << ' ';
}
fout << '\n';
}
}