Pagini recente » Cod sursa (job #289638) | Cod sursa (job #290355) | Cod sursa (job #2264752) | Cod sursa (job #2559956) | Cod sursa (job #2663246)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
const int maxi = 100010;
using namespace std;
int N,M;
vector<int> G[maxi];
vector<int> disc(maxi);
vector<int> lowlink(maxi);
vector <bool> onStack(maxi);
stack<int> s;
vector<vector<int>> sol;
ifstream f("ctc.in");
ofstream g("ctc.out");
void DFS(int node)
{
static int index = 0;
disc[node] = lowlink[node] = index;
index++;
s.push(node);
onStack[node]=true;
for (int it : G[node])
{
if (disc[it]==-1) ///daca nodul nu e vizitat, parcurgem in adancime
DFS(it);
if (onStack[it]==true) ///back-end edge
lowlink[node] = min (lowlink[node],lowlink[it]);
}
if (lowlink[node] == disc[node]) ///inceputul unei componente tare conexe
{
vector <int> v;
while(s.top()!=node)
{
v.push_back(s.top());
onStack[s.top()] == false;
s.pop();
}
v.push_back(node);
onStack[node] = false;
s.pop();
sol.push_back(v);
}
}
int main()
{
f>>N;
f>>M;
int x,y;
for(int i=0;i<M;i++)
{
f>>x>>y;
G[x].push_back(y);
}
/*for(int i=1;i<=N;i++)
{cout<<i<<":";
for(int x: G[i])
cout<<x<<" ";
cout<<endl;}*/
for(int i=1;i<=N;i++)
{
lowlink[i] = -1;
disc[i] = -1;
onStack[i] = false;
}
for(int i=1;i<=N;i++)
if(disc[i] == -1)
DFS(i);
g<<sol.size()<<'\n';
for(auto i: sol)
{for(auto elem:i)
g<<elem<<" ";
g<<'\n';}
return 0;
}