Pagini recente » Cod sursa (job #2414164) | Cod sursa (job #1437303) | Cod sursa (job #2812617) | Cod sursa (job #1739124) | Cod sursa (job #2928827)
//#include <fstream>
//#include <iostream>
//#include <vector>
//#include <stack>
//
//using namespace std;
////Pentru a afla nr de componente tare conexe(pt oricare doua noduri i si j, exista nod de la i la j si de la j la i), voi folosi algoritmul lui kosaraju.
//int N,M, x, y;
//stack<int> stiva;
//vector<vector<int>> lista_adiacenta;
//vector<vector<int>> lista_transpus;
//vector<bool> vizitat_1;
//vector<bool> vizitat_2;
//int nr;
//vector<vector<int>> ctc;
//
//void dfs(int nod){
// vizitat_1[nod]= true;
// for(auto i: lista_adiacenta[nod]){
// if(!vizitat_1[i]) dfs(i);
// }
//
// stiva.push(nod);
//}
//
//void dfs_transpus(int nod){
// ctc[nr].push_back(nod);
// vizitat_2[nod]= true;
// for(auto i: lista_transpus[nod]){
// if(!vizitat_2[i]) dfs_transpus(i);
// }
//}
//
//
//int main(){
// ifstream f("ctc.in");
// ofstream g("ctc.out");
// f>>N>>M;
//
// lista_adiacenta.resize(N+1);
// lista_transpus.resize(N+1);
// vizitat_1.resize(N+1, false);
// vizitat_2.resize(N+1, false);
// ctc.resize(N+1);
//
////formam lista de adiacenta
// for(int i=1; i<=M;i++){
// f>>x>>y;
// lista_adiacenta[x].push_back(y);
// lista_transpus[y].push_back(x);
// }
// f.close();
// dfs(1);
// while(!stiva.empty()){
// int a= stiva.top();
// stiva.pop();
// if(!vizitat_2[a]){nr++;
// dfs_transpus(a);}
// }
//
// g<<nr<<endl;
//
// for(int i=1; i<=nr; i++){
// for(int j=0; j< ctc[i].size(); j++) g<<ctc[i][j]<<" ";
// g<<endl;
// }
// return 0;
//}
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
// matricea de adiacenta a grafului
vector<vector<int>> m;
// matricea transpusa a grafului
vector<vector<int>> m_t;
// vector care determina nivelul unui nod
vector<int> n;
int nr_cc;
// vector unde este stocat rezultatul
vector<vector<int>> cc;
// stiva pentru evidenta nodurilor parcurse la DFS
vector<int> s;
void DFS(int x){
for(auto e: m[x])
if(n[e] == 0){
n[e] = 1;
DFS(e);
}
s.push_back(x);
}
void DFS_T(int x){
cc[nr_cc].push_back(x);
n[x] = 2;
for(auto e: m_t[x])
if(n[e] == 1)
DFS_T(e);
}
int main(){
int N,M,a,b;
// citire
ifstream f("ctc.in");
f>>N>>M;
m.resize(N + 1);
m_t.resize(N + 1);
n.resize(N + 1, 0);
cc.resize(N + 1);
for(int i = 0; i < M; i++){
f>>a>>b;
m[a].push_back(b);
m_t[b].push_back(a);
}
f.close();
for(int i = 1; i <= N; i++){
if(n[i] == 0){
n[i] = 1;
DFS(i);
}
}
while(!s.empty()){
a = s.back();
s.pop_back();
if(n[a] == 1){
nr_cc++;
DFS_T(a);
}
}
ofstream g("ctc.out");
g<<nr_cc<<endl;
for(int i = 1; i <= nr_cc; i++){
for(int j = 0; j < cc[i].size(); j++)
g<<cc[i][j]<<' ';
g<<endl;
}
g.close();
return 0;
}