Pagini recente » Cod sursa (job #1920222) | Cod sursa (job #2986377) | Cod sursa (job #115707) | Cod sursa (job #3235645) | Cod sursa (job #679604)
Cod sursa(job #679604)
#include <fstream>
#include <sstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
typedef struct Nod {
int inf;
struct Nod *next;
} NOD;
typedef struct {
NOD *prim;
} LIST;
#define NMAX 100010
LIST G[NMAX], GT[NMAX];
int N, M, nr=0;
int Plus[NMAX];
int b[NMAX];
void insereaza(LIST *L, int x)
{
NOD* q=new(NOD);
q->inf = x;
q->next = L->prim;
L->prim = q;
}
void dfs(int x)
{
Plus[x] = nr;
for (NOD *q=G[x].prim; q; q=q->next){
if (Plus[q->inf]!=nr && !b[q->inf]){ // daca nodul q nu a fost parcurs si nu face parte dintr-o componenta tare conexa
dfs(q->inf);
}
}
}
stringstream ss;
void dfsT(int x)
{
ss << x << ' ';
b[x] = nr;
for (NOD *q=GT[x].prim; q; q=q->next){
if (Plus[q->inf]==nr && !b[q->inf]){
dfsT(q->inf);
}
}
}
void compTareConexe()
{
int i;
for (i=1; i<=N; i++){
if(!b[i]){
nr++;
dfs(i);
dfsT(i);
ss << '\n';
}
}
g << nr << '\n';
g << ss.str();
}
int main()
{
int x, y;
f >> N >> M;
for (; M--;){
f >> x >> y;
insereaza(&G[x],y);
insereaza(>[y],x);
}
compTareConexe();
return 0;
}