Pagini recente » Cod sursa (job #1235858) | Cod sursa (job #1714833) | Cod sursa (job #1259565) | Cod sursa (job #2423413) | Cod sursa (job #2928899)
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#include <map>
using namespace std;
ifstream fin("graf.in");
ofstream fout("graf.out");
class Graph {
public:
int n;
list<int>* adj_list;
Graph(int n);
void add_edge(int x, int y);
Graph getTranspose();
void DFS(int n,bool visited[]);
void fillOrder(int node, stack<int>& stack, bool visited[]);
void printCTC();
};
//Constructor cu parametru
Graph::Graph(int n)
{
this->n = n;
adj_list = new list <int>[n + 1];
}
//metoda ajutatoare de adaugare de muchii
void Graph:: add_edge( int x, int y)
{
adj_list[x].push_back(y); //adaugam y la lista lui x
}
// parcurgere dfs standard
void Graph:: DFS(int node, bool visited[])
{
visited[node] = true;
fout << node << " ";
list<int>::iterator i;
for (i = adj_list[node].begin(); i != adj_list[node].end(); i++)
if (!visited[*i]) {
DFS(*i, visited);
}
}
// Transpunerea graafului
Graph Graph::getTranspose()
{
Graph g(n);
for (int i = 1; i <= n; i++)
{
list<int>::iterator it;
for (it = adj_list[i].begin(); it != adj_list[i].end(); it++) {
g.adj_list[*it].push_back(i);
}
}
return g;
}
void Graph::fillOrder( int node, stack<int>& stack, bool visited[])
{
//nodul curent devine vizitat
visited[node] = true;
list<int>::iterator i;
for (i = adj_list[node].begin(); i != adj_list[node].end(); i++)
if (!visited[*i]) {
fillOrder( *i, stack, visited);
}
//toate nodurile verificate au fost deja utilizate
stack.push(node);
}
int counter = 0;
void Graph::printCTC()
{
bool* visited = new bool[n];
//marcam toate nodurile la inceput ca nevizitate
stack<int> stack;
for (int i = 1; i <= n; i++)
visited[i] = false;
//punem varfurile in stiva in functie de cum au fost parcursi
for (int i = 1; i <= n; i++)
if (visited[i] == false)
fillOrder( i, stack, visited);
//graf inversat
Graph gr = getTranspose();
for (int i = 1; i <= n; i++)
visited[i] = false;
//Folosim varfurile in functie de cum au intrat in stiva
while (stack.empty() == false)
{
// Luam un varf din stiva
int v = stack.top();
stack.pop();
// Zona unde afisam componentele tari conexe care contin varful
if (visited[v] == false)
{
// Counter pentru a numara componentele tari conexe
counter++;
gr.DFS(v, visited);
fout << endl;
}
}
fout << counter;
}
int main()
{
int n, m;
fin >> n >> m;
Graph g(n);
int x, y;
for (int i = 1; i <= m; i++)
{
do
{
fin >> x >> y;
g.add_edge(x, y);
} while (x < 1 || x > n || y < 1 || y > n || x == y);
}
g.printCTC();
return 0;
}