Pagini recente » Cod sursa (job #771663) | Cod sursa (job #335750) | Cod sursa (job #1434640) | Cod sursa (job #355613) | Cod sursa (job #2692489)
#include<iostream>
#include<list>
#include<stack>
#include<vector>
using namespace std;
vector<int> ps;
vector<vector<int>> ans;
class Graph
{
int v;
list <int>* adj;
void DFS(int v, bool visited[]);
void DFS2(int v, bool visited[],stack<int> &finishtime);
public:
Graph(int v);
void addEdge(int v, int w);
Graph getTranspose();
void printSCC();
};
Graph::Graph(int v)
{
this->v = v;
adj = new list<int>[v];
}
void Graph::DFS(int v, bool visited[])
{
visited[v] = true;
//cout << v << " ";
for (auto it : adj[v])
if (!visited[it])
DFS(it, visited);
ps.push_back(v);
}
void Graph::DFS2(int v, bool visited[], stack<int>& finishtime)
{
visited[v] = true;
for (auto it : adj[v])
if (!visited[it])
DFS2(it, visited,finishtime);
finishtime.push(v);
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
}
Graph Graph::getTranspose()
{
Graph g(v);
for (int i = 0; i < v; i++)
{
for (auto it : adj[i])
g.adj[it].push_back(i);
}
return g;
}
void Graph::printSCC()
{
stack<int> Stack;
bool* visited = new bool[v];
for (int i = 0; i < v; i++)
visited[i] = false;
for (int i = 0; i < v; i++)
if (visited[i] == false)
DFS2(i, visited, Stack);
Graph gr = getTranspose();
for (int i = 0; i < v; i++)
visited[i] = false;
while (!Stack.empty())
{
int v = Stack.top();
Stack.pop();
if (visited[v] == false)
{
ps.clear();
gr.DFS(v, visited);
ans.push_back(ps);
}
}
cout << ans.size()<<endl;
for (auto i : ans)
{
for (auto j : i)
cout << j << " ";
cout << endl;
}
}
int main()
{
int n,m;
cin >> n >> m;
Graph g(n+1);
for (int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
g.addEdge(x, y);
}
//cout << "SCC are:" << endl;
g.printSCC();
}