Pagini recente » Cod sursa (job #2044845) | Cod sursa (job #1323914) | Cod sursa (job #184083) | Cod sursa (job #2260514) | Cod sursa (job #1366147)
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fs first
#define sc second
#define pob pop_back
#define pub push_back
#define eps 1E-7
#define sz(a) a.size()
#define count_one __builtin_popcount;
#define count_onell __builtin_popcountll;
#define fastIO ios_base::sync_with_stdio(false)
#define PI (acos(-1.0))
#define linf (1LL<<62)//>4e18
#define inf (0x7f7f7f7f)//>2e9
#define DEBUG 1
#ifdef DEBUG
#define D(x) x
#else
#define D(x)
#endif
#define MAXN 100001
FILE *in = fopen("ctc.in", "r");
FILE *out = fopen("ctc.out", "w");
struct graph {
int index;
int lowindex;
bool isRemoved;
graph() { this->index = -1; this->lowindex = -1; this->isRemoved = true; }
graph(int a, int b, bool c) {
this->index = a;
this->lowindex = b;
this->isRemoved = c;
}
} *g[MAXN];
int n, m, indecs, tconexe = 0;
stack<int> St;
vector<int> vec[MAXN], elem[MAXN];
void tareConex(int nod) {
//index = 1;
g[nod]->index = indecs;
g[nod]->lowindex = indecs;
indecs++;
g[nod]->isRemoved = false;
St.push(nod);
for(auto it = vec[nod].begin(); it != vec[nod].end(); it++) {
if(g[*it]->index == -1) {
tareConex(*it);
g[nod]->lowindex = min(g[nod]->lowindex, g[*it]->lowindex);
} else {
if(!g[*it]->isRemoved)
g[nod]->lowindex = min(g[nod]->lowindex, g[*it]->index);
}
}
int x;
if(g[nod]->index == g[nod]->lowindex) {
do {
x = St.top(); St.pop();
g[x]->isRemoved = true;
elem[tconexe].pub(x);
} while(x != nod);
tconexe++;
}
}
int main()
{
int x, y;
fscanf(in, "%d%d", &n, &m);
for(int i = 1; i <= m; ++i) {
fscanf(in, "%d%d", &x, &y);
g[i] = new graph();
g[i]->index = -1;
vec[x].pub(y);
}
for(int i = 1; i <= n; ++i) {
if(g[i]->index == -1)
tareConex(i);
}
fprintf(out, "%d\n", tconexe);
for(int i = 0; i < tconexe; ++i) {
for(auto it = elem[i].begin(); it != elem[i].end(); it++)
fprintf(out, "%d ", *it);
fprintf(out, "\n");
}
return 0;
}