Pagini recente » Cod sursa (job #348742) | Cod sursa (job #1253896) | Cod sursa (job #678348) | Cod sursa (job #2662731) | Cod sursa (job #1187281)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#if __cplusplus > 199711L
#include <unordered_map>
#include <unordered_set>
#endif
#include <cstdio>
#include <ctime>
#include <cmath>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef long long int64;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 100010;
int N, M;
int where[NMAX];
vector<int> Gr[NMAX], GrT[NMAX], result[NMAX], discovered;
bitset<NMAX> used;
void DFP(const int &pos)
{
int i, edge;
used[pos] = true;
for (i = 0; i < (int)Gr[pos].size(); ++i)
{
edge = Gr[pos][i];
if (used[edge]) continue;
DFP(edge);
}
discovered.push_back(pos);
}
int main()
{
int x, y, i, j, edge, _edge, value = 0;
queue<int> Q;
fin >> N >> M;
while(M--)
{
fin >> x >> y;
Gr[x].push_back(y);
GrT[y].push_back(x);
}
for (i = 1; i <= N; ++i)
{
if (used[i]) continue;
DFP(i);
}
fill_n(where + 1, N, -1);
for ( ; discovered.size(); discovered.pop_back())
{
if (where[discovered.back()] != -1) continue;
where[discovered.back()] = value;
Q.push(discovered.back());
while(!Q.empty())
{
edge = Q.front(), Q.pop();
for (j = 0; j < (int)GrT[edge].size(); ++j)
{
_edge = GrT[edge][j];
if (where[_edge] != -1) continue;
where[_edge] = value;
Q.push(_edge);
}
}
++value;
}
for (i = 1; i <= N; ++i)
result[where[i]].push_back(i);
fout << value << '\n';
for (i = 0; i < value; ++i)
{
for (j = 0; j < (int)result[i].size(); ++j)
fout << result[i][j] << ' ';
fout << '\n';
}
fin.close();
fout.close();
return 0;
}