Pagini recente » Cod sursa (job #1895209) | Cod sursa (job #368855) | Cod sursa (job #526202) | Cod sursa (job #78272) | Cod sursa (job #396638)
Cod sursa(job #396638)
#include <cstdio>
#include <stack>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
#define DIM 100005
struct nod
{
int x;
bool exista;
nod *next;
};
nod *G[DIM], *Gt[DIM];
int n, m, v[DIM];
stack<int> S;
//set<int> SET[DIM];
vector<int> V[DIM];
void addMuchie(int i, int j, nod *G[])
{
nod *p = new nod;
p->x = j;
p->next = G[i];
G[i] = p;
}
void DFS(int i)
{
v[i] = 1;
for (nod *p = G[i]; p; p = p -> next)
if (!v[p->x])
DFS(p->x);
S.push(i);
}
void DFS2(int i, int count)
{
v[i] = 1;
// SET[count].insert(i);
V[count].push_back(i);
for (nod *p = Gt[i]; p; p = p -> next)
if (!v[p->x])
DFS2(p->x, count);
}
int Count = 0;
void Korasaju()
{
for (int i = 1; i <= n; ++i)
if (!v[i])
DFS(i);
for (int i = 1; i <= n; ++i)
v[i] = 0;
for (; S.size(); S.pop())
{
int x = S.top();
if (!v[x])
DFS2(x, ++Count);
}
}
int main()
{
FILE *f = fopen("ctc.in", "r");
fscanf(f, "%d%d", &n, &m);
for (int x, y;m;--m)
{
fscanf(f, "%d%d", &x, &y);
addMuchie(x, y, G);
addMuchie(y, x, Gt);
}
Korasaju();
f = fopen("ctc.out", "w");
fprintf(f, "%d\n", Count);
// sort(SET+1, SET+Count+1);
for (int i = 1; i <= Count; ++i)
{
// fprintf(f, "%d ",V[i].size());
for (vector<int>::iterator it = V[i].begin(); it != V[i].end(); ++it)
fprintf(f, "%d ", *it);
fprintf(f, "\n");
}
fclose(f);
return 0;
}