Pagini recente » Profil FMI_Andrei_Nazare | Cod sursa (job #2032940) | Monitorul de evaluare | Cod sursa (job #331453) | Cod sursa (job #2142343)
#include <fstream>
#include <vector>
#include <stack>
#define siz 100003
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int lowlink[ siz ], deepth[ siz ], x, y, n, m, nrct = 0,l=1;
bool visited[ siz]{false}, in_stack[siz]{false};
vector < int > v [ siz ],result[siz];
stack < int > st;
void dfs(int i)
{
for(const int& j:v[i])
{
if(!visited[j])
{
deepth[j] = lowlink[j] = ++l;
in_stack[j] = true;
st.push(j);
visited[j] = true;
dfs(j);
lowlink[i] = min(lowlink[i],lowlink[j]);
}
else
if(in_stack[j])
lowlink[i] = min(lowlink[i],lowlink[j]);
}
if( deepth[i] == lowlink[i] )
{
while(st.top()!=i)
{
result[nrct].push_back(st.top());
in_stack[st.top()] = false;
st.pop();
}
result[nrct].push_back(st.top());
in_stack[st.top()]= false;
st.pop();
nrct++;
}
}
int main()
{
int i;
in >> n >> m;
for( i = 0 ; i < m ; i ++)
{
in >> x >> y;
v[x].push_back(y);
}
for( i = 1 ; i <= n ; i ++)
deepth[i] = -1;
for( i = 1 ; i <= n ; i++)
if (deepth[i] == -1)
{
deepth[i] = lowlink[i] = ++l;
in_stack[i] = true;
st.push(i);
visited[i] = true;
dfs(i);
}
out << nrct << "\n";
for( i = 0 ; i < nrct ; i ++)
{
for(const int&e:result[i])
out << e << " ";
out << "\n" ;
}
return 0;
}