Pagini recente » Cod sursa (job #2911373) | Cod sursa (job #735408) | Cod sursa (job #179369) | Cod sursa (job #247415) | Cod sursa (job #2905386)
#include <bits/stdc++.h>
using namespace std;
const int dim = 50005;
template <class T>
class Graph
{
private:
int node_count, edge_count;
vector <T> adj[dim];
vector <T> r_adj[dim];
public:
Graph ()
{
node_count = 0;
edge_count = 0;
}
void Make_Graph (int nodes, int edges)
{
node_count = nodes;
edge_count = edges;
}
void Add_edge (int node1, int node2)
{
adj[node1].push_back(node2);
}
void Add_reverse_edge (int node1, int node2)
{
r_adj[node2].push_back(node1);
}
void Add_weighted_edge(int node1, int node2, int weight)
{
adj[node1].push_back({node2, weight});
}
int NodeNumber ()
{
return node_count;
}
void Afis_Graph ()
{
for (int i = 1; i <= node_count; i++, cout << "\n")
{
cout << i << ": ";
for (int j : adj[i])
cout << j << " ";
}
}
void DFS_SortTop (int node, vector <int> &viz, stack <int> &st)
{
viz[node] = 1;
for (int i : adj[node])
if (!viz[i])
DFS_SortTop(i, viz, st);
st.push(node);
}
void DFS_SCC (int node, vector <int> &viz, vector <int> scc[dim], int nrscc)
{
viz[node] = 0;
for (int i : r_adj[node])
if (viz[i])
DFS_SCC(i, viz, scc, nrscc);
scc[nrscc].push_back(node);
}
stack <int> SortTop (vector <int> &viz, stack <int> &st)
{
for (int i = 1; i <= node_count; i++)
if (!viz[i])
{
DFS_SortTop(i, viz, st);
}
return st;
}
void SCC(vector <int> &viz, stack <int> &st)
{
int nrscc = 0;
stack <int> sol = SortTop(viz, st);
vector <int> scc[dim];
while (!sol.empty())
{
int node = sol.top();
sol.pop();
if (viz[node] == 1)
{
nrscc++;
DFS_SCC(node, viz, scc, nrscc);
}
}
cout << nrscc << "\n";
for (int i = 1; i <= nrscc; i++)
{
for (int j : scc[i])
cout << j << " ";
cout << "\n";
}
}
};
vector <int> viz(dim);
stack <int> st;
stack <int> sol;
Graph <int> G;
void Solve_SortTop()
{
ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");
int n , m;
fin >> n >> m;
G.Make_Graph(n , m);
for (int i = 1; i <= m; i++)
{
int x, y;
fin >> x >> y;
G.Add_edge(x, y);
}
sol = G.SortTop(viz, st);
while (!sol.empty())
{
fout << sol.top() << " ";
sol.pop();
}
}
void Solve_SCC()
{
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int n, m;
fin >> n >> m;
G.Make_Graph(n, m);
for (int i = 1; i <= m; i++)
{
int x, y;
fin >> x >> y;
G.Add_edge(x, y);
G.Add_reverse_edge(x, y);
}
G.SCC(viz, st);
}
int main()
{
Solve_SCC();
return 0;
}