Pagini recente » Cod sursa (job #3294103) | Arhiva Educationala | Cod sursa (job #3286813) | Cod sursa (job #3292770) | Cod sursa (job #3285758)
#include <bits/stdc++.h>
using namespace std;
void DFS1(const vector<vector<int>> &adj, vector<bool> &visited, int s, stack<int> &finishStack)
{
visited[s] = true;
for (int v : adj[s])
if (!visited[v])
DFS1(adj, visited, v, finishStack);
finishStack.push(s);
}
void DFS2(const vector<vector<int>> &adj, vector<bool> &visited, int s, vector<int>¤tComponent)
{
visited[s] = true;
currentComponent.push_back(s);
for (int v : adj[s])
if (!visited[v])
DFS2(adj, visited, v,currentComponent);
}
int kosarajuSCC(const vector<vector<int>> &graph, const vector<vector<int>> &revGraph, int n, vector<vector<int>>&newGraph)
{
stack<int> finishStack;
vector<bool> visited(n + 1, false);
// primul DFS pe graful original pentru a determina ordinea de terminare.
for(int i = 1; i <= n; i++)
if (!visited[i])
DFS1(graph, visited, i, finishStack);
// al doilea DFS pe graful inversat
int sccCount = 0;
fill(visited.begin(), visited.end(), false);
while(!finishStack.empty())
{
int node = finishStack.top();
finishStack.pop();
if (!visited[node])
{
vector<int>currentComponent;
DFS2(revGraph, visited, node,currentComponent);
newGraph.push_back(currentComponent);
sccCount++;
}
}
return sccCount;
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, x, y;
fin >> n >> m;
vector<vector<int>> graph(n + 1), revGraph(n + 1);
for (int i = 0; i < m; i++)
{
fin >> x >> y;
graph[x].push_back(y);
revGraph[y].push_back(x);
}
for (int i = 1; i <= n; i++)
{
sort(graph[i].begin(), graph[i].end());
sort(revGraph[i].begin(), revGraph[i].end());
}
vector<vector<int>>newGraph;
int sccCount = kosarajuSCC(graph, revGraph, n, newGraph);
cout << sccCount << "\n";
for(int i = 0; i < sccCount; i++)
{
for(auto j:newGraph[i])
{
fout <<j<<" ";
}
fout <<"\n";
}
return 0;
}