Pagini recente » Cod sursa (job #2682141) | Cod sursa (job #1432732) | Cod sursa (job #1263617) | Cod sursa (job #1337450) | Cod sursa (job #2926870)
#include <algorithm>
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream o("ctc.out");
int numarNoduri,numarMuchii,x,y,id=0,sscCount=0;
vector<int>la[300000];
vector<int>ids(300000,-1);
vector<int>low(300000,0);
vector<bool>onStack(300000,false);
vector<int>raspuns[300000];
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();
o<<sscCount<<"\n";
for(int i=0;i<sscCount;i++){
sort(raspuns[i].begin(),raspuns[i].end());
for(auto a:raspuns[i])
o<<a<<" ";
o<<endl;
}
return 0;
}