Pagini recente » Cod sursa (job #1419343) | Cod sursa (job #1613262) | Cod sursa (job #1244413) | Cod sursa (job #3039269) | Cod sursa (job #2926863)
#include <algorithm>
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
ifstream f("ctc.in");
int numarNoduri,numarMuchii,x,y,id=0,sscCount=0;
vector<int>la[6000];
vector<int>ids(6000,-1);
vector<int>low(6000,0);
vector<bool>onStack(6000,false);
vector<int>raspuns[6];
stack<int>myStack;
void DFS(int at){
myStack.push(at);
onStack[at]=true;
ids[at]=low[at]=id++;
for(auto to:la[at])
{
if(ids[to]==-1)
DFS(to);
if(onStack[to])
low[at]=min(low[at],low[to]);
}
if(ids[at]==low[at]){
int node=myStack.top();
myStack.pop();
while(node!=at){
raspuns[sscCount].push_back(node);
onStack[node]=false;
low[node]=ids[at];
node=myStack.top();
myStack.pop();
}
onStack[node]=false;
low[node]=ids[at];
raspuns[sscCount].push_back(node);
sscCount++;
}
}
void findSccs(){
for(int i=1;i<=numarNoduri;i++)
if(ids[i]==-1)
DFS(i);
}
int main() {
f>>numarNoduri>>numarMuchii;
while(f>>x&&f>>y)
la[x].push_back(y);
findSccs();
cout<<sscCount<<"\n";
for(int i=0;i<sscCount;i++){
sort(raspuns[i].begin(),raspuns[i].end());
for(auto a:raspuns[i])
cout<<a<<" ";
cout<<endl;
}
return 0;
}