Pagini recente » Cod sursa (job #2420507) | Cod sursa (job #591167) | Cod sursa (job #1604665) | Cod sursa (job #478781) | Cod sursa (job #251096)
Cod sursa(job #251096)
//tarjan - cel mai bun
# include <cstdio>
# include <vector>
using namespace std;
# define FIN "ctc.in"
# define FOUT "ctc.out"
# define min(a, b) (a < b ? a : b)
# define MAXN 100005
int N, M, i, vf, ct, Time;
int St[MAXN];
int Lvl[MAXN];
int Low[MAXN];
vector <int> G[MAXN];
vector <int> CTC[MAXN];
void Dfs(int nod)
{
vector <int> :: iterator it;
St[++vf] = nod;
Lvl[nod] = Low[nod] = ++Time;
for (it = G[nod].begin(); it != G[nod].end(); ++it)
{
if (!Lvl[*it])
{
Dfs(*it);
Low[nod] = min(Low[nod], Low[*it]);
} else
if (Lvl[*it] > 0)
Low[nod] = min(Low[nod], Lvl[*it]);
}
if (Low[nod] == Lvl[nod])
{
++ct;
for (i = vf; St[i + 1] != nod; --i)
{
CTC[ct].push_back(St[i]);
Lvl[St[i]] = -1;
}
vf = i;
}
}
int main()
{
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%d %d",&N, &M);
for (i = 1; i <= M; ++i)
{
int x, y;
scanf("%d %d",&x, &y);
G[x].push_back(y);
}
vf = ct = Time = 0;
for (i = 1; i <= N; ++i)
if (!Lvl[i]) Dfs(i);
printf("%d\n",ct);
vector <int> :: iterator it;
for (i = 1; i <= ct; ++i)
{
for (it = CTC[i].begin(); it != CTC[i].end(); ++it)
printf("%d ",*it);
printf("\n");
}
return 0;
}