Pagini recente » Cod sursa (job #1401619) | Cod sursa (job #69360) | Cod sursa (job #578057) | Cod sursa (job #1784013) | Cod sursa (job #2927305)
#include<iostream>
#include<fstream>
#include<unordered_map>
#include<vector>
#include<stack>
using namespace std;
int n, m, n1, n2, i;
int id = 0, scc = 0;
vector<vector<int>>lista;
unordered_map<int, int>index;
unordered_map<int, int>low;
unordered_map<int, bool>on_stack;
vector<vector<int>> final;
stack<int>s;
ifstream f("ctc.in");
ofstream g("ctc.out");
void DFS(int root) {
low[root] = ++id;
index[root] = low[root];
s.push(root);
on_stack[root] = 1;
for (auto el : lista[root])
{
if (index[el] == 0)
DFS(el);
if (on_stack[el])
low[root] = min(low[root], low[el]);
}
if (low[root] == index[root])
{
vector<int>sec;
while (!s.empty()) {
on_stack[s.top()] = false;
sec.push_back(s.top());
s.pop();
if (s.top() == root) {
sec.push_back(s.top());
break;
}
}
final.push_back(sec);
scc++;
}
}
int main() {
f >> n >> m;
lista.resize(n + 1);
for (int i = 1; i <= m; i++) {
f >> n1 >> n2;
lista[n1].push_back(n2);
}
for (i = 1; i <= n; i++)
if (index[i] == 0)
DFS(i);
g << scc << "\n";
for (auto sec : final)
{
for (auto nr : sec)
g << nr << " ";
g << "\n";
}
}