Pagini recente » Cod sursa (job #1340142) | Cod sursa (job #1481917) | Cod sursa (job #1249166) | Cod sursa (job #1593848) | Cod sursa (job #1415436)
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_set>
#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;
unordered_set < int > se[siz];
bool visited[ siz],in_stack[siz];
vector < int > v [ siz ];
stack < int > st;
void dfs(int i,int l)
{
int j;
deepth[i] = l;
lowlink[i] = l;
in_stack[i] = true;
st.push(i);
visited[i] = true;
for(auto it = v[i].begin(); it !=v[i].end(); it++)
{
j = *it;
if(!visited[j])
{
dfs(j,l+1);
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)
{
se[nrct].insert(st.top());
in_stack[st.top()] = false;
st.pop();
}
se[nrct].insert(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;
visited[i] = false;
in_stack[i] = false;
}
for( i = 1 ; i <= n ; i++)
if (deepth[i] == -1)
dfs(i,1);
out << nrct << "\n";
for( i = 0 ; i < nrct ; i ++)
{
for( auto it = se[i].begin(); it != se[i].end() ; it ++)
out << *it << " ";
out << "\n" ;
}
return 0;
}