Pagini recente » Cod sursa (job #879889) | Cod sursa (job #3180152) | Cod sursa (job #711669) | Cod sursa (job #2856330) | Cod sursa (job #2839108)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
typedef struct graf {
int x;
graf* a;
}*L;
L a[100001];
L at[100001];
int stiva[100001];
int vf = 0;
int f[100001];
int ctc[100001];
int ctcord[100001];
int ans = 0;
vector <int> rez[100001];
int n, m;
void adaugare(L& dest, int val)
{
L aux = new graf;
aux->x = val;
aux->a = dest;
dest = aux;
}
void citire()
{
int x, y;
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
fin >> x >> y;
adaugare(a[x], y);
adaugare(at[y], x);
}
}
void dfs1(int nod)
{
f[nod] = 1;
for (L p = a[nod]; p != NULL; p = p->a)
{
if (!f[p->x]) {
dfs1(p->x);
}
}
stiva[++vf] = nod;
}
void dfs2(int nod,int nrcomp)
{
ctc[nod] = nrcomp;
for (L p = at[nod]; p != NULL; p = p->a) {
if (ctc[p->x]==0) {
dfs2(p->x, nrcomp);
}
}
}
void Kosaraju() {
for (int i = 1; i <= n; i++) {
if (!f[i]) dfs1(i);
}
while (vf > 0)
{
int k = stiva[vf--];
if (!ctc[k]) {
ans++;
dfs2(k, ans);
}
}
//fout << ans;
}
void ordonare()
{
int aux =1;
for (int i = 1; i <= n; i++)
{
if (ctc[i] == ctc[i + 1]) {
ctcord[i] = ctcord[i + 1] = aux;
}
else {
aux++;
ctcord[i + 1] = aux;
}
}
fout << ans << '\n';
for (int i = 1; i <= ans; i++)
{
for (int j = 1; j <= n; j++)
{
if (ctcord[j] == i) fout << j << ' ';
}
fout << '\n';
}
}
void new_graf()
{
Kosaraju();
ordonare();
}
int main()
{
citire();
new_graf();
}