Pagini recente » Cod sursa (job #892350) | Cod sursa (job #2782066) | Cod sursa (job #2487638) | Cod sursa (job #287872) | Cod sursa (job #526943)
Cod sursa(job #526943)
#include<cstdio>
#include<stack>
using namespace std;
struct list {
int neigh;
list *next;
};
list *graf[100001];
list *grafRev[100001];
list *compCon[100001];
bool viz[100001];
int N, M;
int compconex;
stack<int> stackNodes;
void readData() {
scanf("%d %d", &N, &M);
int x, y;
for (int i = 0; i < M; i++) {
scanf("%d %d ", &x, &y);
list *aux = new list;
aux->neigh = y;
aux->next = graf[x];
graf[x] = aux;
aux = new list;
aux->neigh = x;
aux->next = grafRev[y];
grafRev[y] = aux;
}
}
void dfs(int source){
viz[source] = 1;
list *aux = graf[source];
while (aux) {
if (!viz[aux->neigh]) {
dfs(aux->neigh);
}
aux = aux->next;
}
stackNodes.push(source);
}
void dft(int source){
viz[source] = 0;
list *add = new list;
add->neigh = source;
add->next = compCon[compconex];
compCon[compconex] = add;
list *aux = grafRev[source];
while (aux) {
if (viz[aux->neigh]) {
dft(aux->neigh);
}
aux = aux->next;
}
stackNodes.push(source);
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
readData();
for (int i = 1; i <= N; i++) {
if (!viz[i]) {
dfs(i);
}
}
int x;
compconex = 0;
while (!stackNodes.empty()) {
x = stackNodes.top();
stackNodes.pop();
if (viz[x]){
dft(x);
compconex++;
}
}
printf("%d\n",compconex);
for (int i = 0; i < compconex; i++) {
list *aux = compCon[i];
while (aux){
printf("%d ", aux->neigh);
aux = aux->next;
}
printf("\n");
}
return 0;
}