Pagini recente » Cod sursa (job #3236954) | Cod sursa (job #2879382) | Cod sursa (job #2930501) | Cod sursa (job #573534) | Cod sursa (job #3269800)
#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> num;
std::vector<int> minim;
std::vector<int> viz;
std::vector<int> processed;
std::stack<int> s;
std::vector<std::vector<int>> rez;
int i = 0;
void scc(int node)
{
num[node] = i;
minim[node] = i;
i++;
viz[node] = 1;
s.push(node);
for(int x : nums[node])
{
if(!viz[x])
{
scc(x);
minim[node] = std::min(minim[node], minim[x]);
}
else if(!processed[x])
{
minim[node] = std::min(minim[node], minim[x]);
}
}
processed[node] = 1;
if(minim[node] == num[node])
{
std::set<int> st;
int sccCurent = s.top(); s.pop();
while(sccCurent != node)
{
st.insert(sccCurent);
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);
processed.resize(n + 1);
num.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';
}
}