Pagini recente » Cod sursa (job #2298761) | Cod sursa (job #2346369) | Cod sursa (job #1389758) | Cod sursa (job #1494908) | Cod sursa (job #2925282)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;
int id, lowViz[NMAX + 5];
void getComp(int nod, vector<vector<int>> &compList, bool onStack[], stack<int> &stackNodes) {
vector<int> comp;
while(stackNodes.top() != nod) {
comp.emplace_back(stackNodes.top());
onStack[stackNodes.top()] = 0;
stackNodes.pop();
}
comp.emplace_back(nod);
onStack[nod] = 0;
stackNodes.pop();
compList.push_back(comp);
}
void dfs(int nod, vector<int> G[], int viz[], bool onStack[], vector<vector<int>> &compList, stack<int> &stackNodes) {
viz[nod] = lowViz[nod] = ++id;
onStack[nod] = 1;
stackNodes.push(nod);
for(auto &vec : G[nod]) {
if(onStack[vec]) {
lowViz[nod] = min(lowViz[nod], viz[vec]);
} else if(!viz[vec]) {
dfs(vec, G, viz, onStack, compList, stackNodes);
lowViz[nod] = min(lowViz[nod], lowViz[vec]);
}
}
if(viz[nod] == lowViz[nod])
getComp(nod, compList, onStack, stackNodes);
}
int main()
{
ios::sync_with_stdio(false);
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
fin >> n >> m;
vector<int> G[n + 1];
for(int i = 1; i <= m; i++) {
int a, b;
fin >> a >> b;
G[a].emplace_back(b);
}
int viz[n + 1];
bool onStack[n + 1];
for(int i = 1; i <= n; i++)
viz[i] = onStack[i] = 0;
vector<vector<int>> compList;
stack<int> stackNodes;
for(int i = 1; i <= n; i++)
if(!viz[i])
dfs(i, G, viz, onStack, compList, stackNodes);
fout << compList.size() << '\n';
for(auto &comp : compList) {
for(auto &nod : comp)
fout << nod << " ";
fout << '\n';
}
fin.close();
fout.close();
return 0;
}