Pagini recente » Cod sursa (job #2958762) | Cod sursa (job #2742508) | Cod sursa (job #2927395)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
//4. elementele tare conexe intr-un graf orientat:
//elementele tare conexe sunt cele in care se formeaza cicluri, deci trebuie sa cautam ciclurile, adica seturile de noduri in care
//putem sa ne plimbam prin noduri => fiecare nod este si extremitate finala si extremitate initiala pentru cate un arc;
//intr-o parcurgere DF, un nod este extremitate finala pentru un arc care incepe intr-un nod din stanga lui, deci o sa pargurg DF
//graful memorand cu ajutorul unei stive ordinea parcurgerii;
//voi folosi stackul pentru a lua cate o extremitate finala si a verifica daca ea este si extremitate initiala, parcurgand DF;
//parcurgerile noi sunt chiar componentele tare conexe;
//complexitate: O(n+m) = 2 parcurgeri DF, unde n=numarul de varfuri, m=numarul de muchii
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
vector<vector<int>> adj, scc;
vector<int> visited, temp;
stack<int> preorder;
//prima parcurgere DF, care memoreaza pe stack ordinea:
void DFS1(int node) {
visited[node] = 1;
preorder.push(node);
for (int i = 0; i < adj[node].size(); i++)
if (visited[node] == 0)
DFS1(node);
}
//a doua parcurgere DF, care memoreaza ciclul curent in vectorul "temp":
void DFS2(int node) {
visited[node] = 1;
temp.push_back(node);
for (int i = 0; i < adj[node].size(); i++)
if (visited[adj[node][i]] == 0)
DFS2(adj[node][i]);
}
//functia care cauta componentele tare conexe:
void SCC() {
//prima parcurgere:
for (int i = 1; i <= n; i++)
if (visited[i] == 0)
DFS1(i);
visited.clear();
visited.resize(n + 1, 0);
//a doua parcurgere:
while (!preorder.empty()) {
if (visited[preorder.top()] == 0) {
DFS2(preorder.top());
//memorarea ciclului din "temp" ca componenta tare conexa:
scc.push_back(temp);
temp.clear();
}
preorder.pop();
}
}
int main()
{
fin >> n >> m;
adj.resize(n+1);
visited.resize(n+1, 0);
//stocarea datelor de intrare intr-o lista de adiacenta:
for (int i = 0; i < m; i++) {
int node1, node2;
fin >> node1 >> node2;
adj[node1].push_back(node2);
}
//apelarea functiei care cauta componentele tare conexe:
SCC();
//afisarea rezultatului:
fout << scc.size() << "\n";
for (int i = 0; i < scc.size(); i++) {
for (int j = 0; j < scc[i].size(); j++)
fout << scc[i][j] << " ";
fout << "\n";
}
fin.close();
fout.close();
return 0;
}