Pagini recente » Cod sursa (job #973572) | Cod sursa (job #2979272) | Cod sursa (job #983520) | Cod sursa (job #1923811) | Cod sursa (job #921602)
Cod sursa(job #921602)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#define NMAX 100005
#define FILEIN "ctc.in"
#define FILEOUT "ctc.out"
using namespace std;
vector<int> V[NMAX];
int idx[NMAX];
int lowlink[NMAX];
int in_st[NMAX];
vector<vector<int> > sol;
vector<int> ctc;
stack<int> st;
int indice;
inline int min(int a, int b)
{
return a < b ? a : b;
}
void tarjan( int node )
{
int i;
idx[node] = indice;
lowlink[node] = indice;
indice++;
st.push(node);
in_st[node] = 1;
for ( i = 0; i < V[node].size(); i++)
{
if(idx[V[node][i]] == -1)
{
tarjan(V[node][i]);
lowlink[node] = min(lowlink[node], lowlink[V[node][i]]);
}
else
if(in_st[V[node][i]] == 1)
{
lowlink[node] = min(lowlink[node], lowlink[V[node][i]]);
}
}
if(idx[node] == lowlink[node])
{
ctc.clear();
int tmp;
do
{
tmp = st.top(), in_st[tmp] = 0, ctc.push_back(tmp);
st.pop();
}
while(tmp != node);
sol.push_back(ctc);
}
}
int main()
{
int n, m,i,j,x,y;
freopen(FILEIN,"r",stdin);
freopen(FILEOUT,"w",stdout);
scanf("%d %d", &n, &m);
for ( i = 1; i <= m; i++ )
{
scanf("%d %d", &x, &y);
V[x].push_back(y);
}
for ( i = 1; i <= n; i++ )
idx[i] = -1;
for ( i = 1; i <= n; i++ )
if(idx[i] == -1)
tarjan(i);
printf("%d\n",sol.size());
for ( i = 0; i < sol.size(); i++)
{
for ( j = 0; j < sol[i].size(); j++)
printf("%d ", sol[i][j]);
printf("\n");
}
return 0;
}