Pagini recente » Cod sursa (job #1768405) | Cod sursa (job #669931) | Cod sursa (job #2111431) | Cod sursa (job #1129024) | Cod sursa (job #2839059)
#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 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 dfs(int nod, int nrcomp)
{
f[nod] = nrcomp;
rez[nrcomp].push_back(nod);
for (L p = at[nod]; p != NULL; p = p->a)
{
if (!f[p->x])
dfs(p->x, nrcomp);
}
}
void componente_tari_conexe() {
for (int i = 1; i <= n; i++) {
if (!f[i]) dfs1(i);
}
for (int i = 1; i <= n; i++) f[i] = 0;
while (vf > 0)
{
int k = stiva[vf--];
if (!f[k])
{
ans++;
dfs(k, ans);
}
}
fout << ans << '\n';
for (int i = 1; i <= ans; i++)
{
for (int j = 0; j <rez[i].size(); j++)
fout << rez[i][j] << ' ';
fout << '\n';
}
}
int main()
{
citire();
componente_tari_conexe();
}