Pagini recente » Cod sursa (job #676248) | Cod sursa (job #1140212) | Cod sursa (job #1441220) | Cod sursa (job #756682) | Cod sursa (job #2796389)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
class Graph
{
private:
int verticesNo;
int edgesNo;
bool oriented;
vector<vector<int>> adjacencyList;
public:
Graph();
Graph(int verticesNo, int edgesNo, bool oriented);
void bfs(int start); //BFS
void dfs(int vertex, vector<int> &visited); //DFS
void dfsB(int vertex, vector<int> &visitedB); //CTC
void dfsWstack(int vertex, vector<int> &visited, stack<int> &st);
void stronglyConnectedComponents();
int connectedComponentsNo(); //DFS
void topologicalSort();
virtual ~Graph();
};
Graph::Graph()
{
verticesNo = edgesNo = oriented = 0;
this->adjacencyList.clear();
}
Graph::Graph(int verticesNo, int edgesNo, bool oriented)
{
this->verticesNo = verticesNo;
this->edgesNo = edgesNo;
this->oriented = oriented;
this->adjacencyList.resize(verticesNo + 1);
int vertex1, vertex2;
for(int i = 0; i < this->edgesNo; i++)
{
fin>>vertex1>>vertex2;
this->adjacencyList[vertex1].push_back(vertex2);
if(this->oriented == 0)
this->adjacencyList[vertex2].push_back(vertex1);
}
}
Graph::~Graph()
{
this->adjacencyList.clear();
}
void Graph::bfs(int start)
{
int n = this->verticesNo;
vector<int> visited;
vector<int> distances;
queue<int> order;
order.push(start);
for(int i = 0; i <= n; i++)
{
visited.push_back(0);
distances.push_back(-1);
}
distances[start] = 0;
visited[start] = 1;
while(!order.empty())
{
int current = order.front();
int sz = adjacencyList[current].size();
order.pop();
for(int i = 0; i < sz; i++)
{
int temp = adjacencyList[current][i];
if(visited[temp] == 0)
{
visited[temp] = 1;
order.push(temp);
distances[temp] = distances[current]+1;
}
}
}
for(int i = 1; i < distances.size(); i++)
fout<<distances[i]<<" ";
}
void Graph::dfs(int vertex, vector<int> &visited)
{
visited[vertex] = 1;
int sz = adjacencyList[vertex].size();
for(int i = 0; i < sz; i++)
{
if(visited[adjacencyList[vertex][i]] == 0)
dfs(adjacencyList[vertex][i],visited);
}
}
int Graph::connectedComponentsNo()
{
vector<int> visited;
int ccn = 0; //no of connected components
for(int i = 0 ; i <= this->verticesNo; i++)
visited.push_back(0);
for(int i = 1; i <= this->verticesNo; i++)
if(visited[i] == 0)
{
dfs(i,visited);
ccn++;
}
return ccn;
}
void Graph::dfsB(int vertex, vector<int> &visitedB)
{
visitedB[vertex] = 1;
int sz = this->verticesNo;
for(int i = 0; i <= sz; i++)
{
if(visitedB[adjacencyList[i][vertex]] == 0)
{cout<<"jale2\n";
dfs(adjacencyList[i][vertex],visitedB);
}
}
}
void Graph::stronglyConnectedComponents()
{
vector<int> visited;
vector<int> visitedB;
vector<int> scc;
int sccNo = 0;
for(int i = 0 ; i <= this->verticesNo; i++)
scc.push_back(0);
for(int i = 1 ; i <= this->verticesNo; i++)
if(scc[i] == 0)
{
for(int j = 0; j <= this->verticesNo; j++)
{
visited.push_back(0);
visitedB.push_back(0);
}
sccNo++;
dfs(i,visited);cout<<"jale";
dfsB(i,visitedB);
for(int k = 1; k <= this->verticesNo; k++)
{
if(visited[k] == 1 && visitedB[k] == 1)
scc[k] = sccNo;
}
}
cout<<sccNo<<"\n";
for(int i = 1; i <= this->verticesNo; i++)
cout<<scc[i]<<" ";
}
void Graph::dfsWstack(int vertex, vector<int> &visited, stack<int> &st)
{
visited[vertex] = 1;
int sz = adjacencyList[vertex].size();
for(int i = 0; i < sz; i++)
{
if(visited[adjacencyList[vertex][i]] == 0)
dfsWstack(adjacencyList[vertex][i],visited,st);
}
st.push(vertex);
}
void Graph::topologicalSort()
{
stack<int> st;
vector<int> visited;
for(int i = 0; i <= this->verticesNo; i++)
visited.push_back(0);
for(int i = 1 ; i <=this->verticesNo; i++)
if(visited[i] == 0)
dfsWstack(i,visited,st);
while(!st.empty())
{
fout<<st.top()<<" ";
st.pop();
}
}
int main()
{
int N,M;
fin>>N>>M;
Graph top(N,M,1);
top.topologicalSort();
return 0;
}