Pagini recente » Cod sursa (job #468997) | Cod sursa (job #364462) | Cod sursa (job #2779082) | Cod sursa (job #2981135) | Cod sursa (job #2930615)
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <stack>
using namespace std;
class Graph{
list<int> *adj; // un array de liste de adiacente
int V; // nr. de noduri
public:
Graph(int V=0);
Graph& operator=(const Graph& ob);
void addEdge(int v, int w);
void print() const;
friend ostream& operator<<(ostream& out, const Graph& ob);
void printSCC();
Graph getTranspose();
void firstDFS(int v, bool visited[], stack<int>& Stack);
void secondDFS(int v, bool visited[], vector<int>& SCC);
};
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V+1];
}
Graph& Graph::operator=(const Graph& ob){
if(this != &ob) {
this->V = ob.V;
this->adj = new list<int>[ob.V + 1];
for (int i = 1; i <= V; i++)
for (auto it: ob.adj[i])
this->addEdge(it, i);
}
return *this;
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}
void Graph::print() const {
for (int i = 1; i <= V; i++) {
cout << i << ": ";
for (auto e: adj[i])
cout << e << " ";
cout << endl;
}
}
ostream& operator<<(ostream& out, const Graph& ob){
ob.print();
return out;
}
Graph Graph::getTranspose(){
Graph gT(V);
for(int e = 1; e <= V; e++)
for(auto v: adj[e])
gT.addEdge(e, v);
return gT;
}
void Graph::firstDFS(int v, bool visited[], stack<int>& Stack){
visited[v] = true;
for(auto e: adj[v]){
if(!visited[e])
firstDFS(e, visited, Stack);
}
Stack.push(v);
}
void Graph::secondDFS(int v, bool visited[], vector<int>& SCC){
SCC.push_back(v);
visited[v] = true;
for(auto e: adj[v])
if(!visited[e])
secondDFS(e, visited, SCC);
}
ofstream fout("ctc.out");
void Graph::printSCC() {
vector<vector<int>> allSCC;
stack<int> Stack;
bool *visited = new bool[V+1];
for(int i = 1; i <= V; i++)
visited[i] = false;
for(int i = 1; i <= V; i++)
if(!visited[i])
firstDFS(i, visited, Stack);
//Generam graful transpus al lui g
Graph gT;
gT = this->getTranspose();
for(int i = 1; i <= V; i++)
visited[i] = false;
while(!Stack.empty()){
int v = Stack.top();
Stack.pop();
if(!visited[v]) {
vector<int> SCC;
gT.secondDFS(v, visited, SCC);
allSCC.push_back(SCC);
}
}
fout << allSCC.size() << endl;
for(const auto &i: allSCC){
for(const auto &v: i)
fout << v << ' ';
fout << endl;
}
}
int main(){
ifstream fin("ctc.in");
int V, E;
// Citim graful g
fin >> V >> E;
Graph g(V);
for(int i = 0; i < E; i++) {
int v, w;
fin >> v >> w;
g.addEdge(v, w);
}
g.printSCC();
fout.close();
}