Pagini recente » Cod sursa (job #1972298) | Cod sursa (job #1621852) | Cod sursa (job #2726414) | Cod sursa (job #2864918) | Cod sursa (job #2927468)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
//4. elementele tare conexe intr-un graf orientat:
//proprietate a componentelor tare conexe in graful transpus: daca un nod este reachable din altul si in graful initial si in cel transpus
//(un ciclu ramane un ciclu si in graful transpus), atunci e clar ca ele se afla in aceeasi componenta conexa;
//astfel, facem 2 parcurgeri DF, una pe graful initial si una pe graful transpus;
//prima parcurgere este retinuta pe un stack in ordine inversa parcurgerii, pentru ca daca un nod e la final, asta inseamna ca el este
//extremitate initiala pentru un arc, iar parcurgerea pe graful transpus ne va asigura ca exista si extremitate finala, extremitatile finale
//devenind extremitati initiale pe graful traspus, deci locuri de pornire pentru DF;
//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, adjTrans;
vector<int> visited, temp;
stack<int> order;
//prima parcurgere DF, care memoreaza pe stack ordinea:
void DFS1(int node) {
visited[node] = 1;
for (int i = 0; i < adj[node].size(); i++)
if (visited[adj[node][i]] == 0)
DFS1(adj[node][i]);
order.push(node);
}
//a doua parcurgere DF, care memoreaza componenta tare conexa curenta in vectorul "temp":
void DFS2(int node) {
visited[node] = 1;
temp.push_back(node);
for (int i = 0; i < adjTrans[node].size(); i++)
if (visited[adjTrans[node][i]] == 0)
DFS2(adjTrans[node][i]);
}
//tranpunerea listei de adiacenta:
void transpose() {
adjTrans.resize(n + 1);
for (int i = 0; i < adj.size(); i++)
for(int j=0; j<adj[i].size(); j++)
adjTrans[adj[i][j]].push_back(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);
//transpunerea:
transpose();
//a doua parcurgere:
while (!order.empty()) {
if (visited[order.top()] == 0) {
DFS2(order.top());
//memorarea ciclului din "temp" ca componenta tare conexa:
scc.push_back(temp);
temp.clear();
}
order.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;
}