Pagini recente » Cod sursa (job #1509279) | Cod sursa (job #2377566) | Cod sursa (job #2178491) | Cod sursa (job #2370990) | Cod sursa (job #2792084)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<vector<int>> Componente;
int timeG = 1;
struct GraphTimeStamps{
int entert = -1;
int leavet = -1;
int low_link = -1;
};
void dfs(int node, vector<int>* G, GraphTimeStamps* GTS, stack<int>& s, bool* onStack ){
s.push(node);
onStack[node] = true;
GTS[node].low_link = timeG;
GTS[node].entert = GTS[node].low_link;
timeG++;
for(auto vecin:G[node]){
if(GTS[vecin].entert==-1){ // inseamna ca vecinul respectiv nu e vizitat
// cout<<"vizitam "<<vecin<<endl;
dfs(vecin, G, GTS,s,onStack);
// cout<<"am terminat de vizitat "<<vecin<<endl;
GTS[node].low_link = min(GTS[node].low_link,GTS[vecin].low_link);
}
else if(onStack[vecin]){ // inseamna ca vecinul este pe stiva deci face parte din aceeasi componenta conexa
// cout<<"nu mai vizitam "<<vecin<<"pentru ca este deja pe stiva \n";
GTS[node].low_link = min(GTS[node].low_link,GTS[vecin].entert);
}
}
GTS[node].leavet = timeG++;
if(GTS[node].entert == GTS[node].low_link){
vector<int> temp;
while(s.top()!=node){
temp.push_back(s.top()+1);
int topElem = s.top();
onStack[topElem] = false;
GTS[topElem].low_link = GTS[node].low_link;
s.pop();
}
temp.push_back(s.top()+1);
int topElem = s.top();
onStack[topElem] = false;
s.pop();
Componente.push_back(temp);
}
}
int main(){
int n,m;
in>>n>>m;
vector<int> G[n];
GraphTimeStamps GTS[n];
stack<int> s;
bool onStack[n]{(false)};
for(int i = 0;i<m;i++){
int x,y;
in>>x>>y;
G[x-1].push_back(y-1);
}
// afisare listei de adiacenta
// for(int i = 0;i<n;i++){
// cout<<i<<" : ";
// for(auto node:G[i]){
// cout<<node<<" ";
// }
// cout<<endl;
// }
for(int i=0;i<n;i++){
if(GTS[i].entert == -1){
dfs(0,G,GTS,s,onStack);
}
}
out<<Componente.size()<<'\n';
for(auto cc:Componente){
for(auto node:cc){
out<<node<<" ";
}
out<<'\n';
}
// for(auto elem : GTS){
// cout<<elem.entert<<" ";
//
// }
// cout<<endl;
// for(auto elem : GTS){
// cout<<elem.leavet<<" ";
// }
//
// cout<<endl;
// for(auto elem : GTS){
// cout<<elem.low_link<<" ";
// }
}