Pagini recente » Cod sursa (job #765816) | Cod sursa (job #809237) | Cod sursa (job #796148) | Cod sursa (job #586604) | Cod sursa (job #3295782)
#include <complex>
#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <vector>
#define INF 1e9
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int ctc;
vector<vector<int>> scc;
bool is_in_stack(int node, vector<int> &stack)
{
for (int i = 0; i < stack.size(); ++i) {
if (stack[i] == node)
return true;
}
return false;
}
void DFS(int node,int ×tamp, vector<vector<int>> &adj, vector<int> &parent,
vector<int> &viz, vector<int> &low_link, vector<int> &stack)
{
viz[node] = ++timestamp;
low_link[node] = viz[node];
stack.push_back(node);
for (int neigh : adj[node]) {
if (parent[neigh] > 0) {
if (is_in_stack(neigh, stack))
low_link[node] = min(low_link[node], viz[neigh]);
continue;
}
parent[neigh] = node;
DFS(neigh, timestamp, adj, parent, viz, low_link, stack);
low_link[node] = min (low_link[node], low_link[neigh]);
}
if (low_link[node] == viz[node]) {
vector<int> comp;
int x;
do {
cout << " printez\n";
x = stack.back();
stack.pop_back();
comp.push_back(x);
} while (x != node);
ctc++;
scc.push_back(comp);
}
}
void tarzan(int N, vector<vector<int>> &adj)
{
vector<int> parent (N + 1, -1);
vector<int> viz (N + 1, INF);
vector<int>low_link(N + 1, INF);
vector<int> stack;
int timestamp = 0;
for (int i = 1; i <= N; ++i)
{
if (parent[i] < 0) {
cout << i << '\n';
parent[i] = i;
cout<< "apelez dfs\n";
DFS(i, timestamp, adj, parent, viz, low_link, stack);
cout << "ise din dfs\n";
}
}
}
int main()
{
int N, M;
fin >> N >> M;
vector<vector<int>> adj(N + 1, vector<int>());
for (int i = 0; i < M; ++i) {
int x, y;
fin >> x >> y;
adj[x].push_back(y);
}
tarzan(N, adj);
cout<<"ies din tarzazn\n";
fout << ctc << '\n';
for (int i = 0; i < ctc; ++i) {
for (int j = 0; j < scc[i].size(); ++j)
fout << scc[i][j] << ' ';
fout << '\n';
}
return 0;
}