Pagini recente » Cod sursa (job #433232) | Cod sursa (job #214223) | Cod sursa (job #268059) | Cod sursa (job #1071005) | Cod sursa (job #679520)
Cod sursa(job #679520)
#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;
int Plus[NMAX];
int Minus[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 afis(LIST *L)
{
for(NOD* q=L->prim; q; q=q->next){
g << q->inf << ' ';
}
g << '\n';
}
void dfs(LIST G[],int x,int a[],int p, int b[])
{
a[x] = p;
for (NOD *q=G[x].prim; q; q=q->next){
if (a[q->inf]!=p && !b[q->inf]){
dfs(G,q->inf,a,p,b);
}
}
}
void compTareConexe()
{
stringstream ss;
int i, j, nr=0;
for (i=1; i<=N; i++){
if(!b[i]){
nr++;
dfs(G,i,Plus,nr,b);
dfs(GT,i,Minus,nr,b);
for (j=1; j<=N; j++){
if (Plus[j]==nr && Minus[j]==nr){
ss << j << ' ';
b[j] = nr;
}
}
ss << '\n';
}
}
g << nr << '\n';
g << ss.str();
}
int main()
{
int i, x, y;
f >> N >> M;
for (i=0; i<M; i++){
f >> x >> y;
insereaza(&G[x],y);
insereaza(>[y],x);
}
//afis(>[3]);
compTareConexe();
return 0;
}