Pagini recente » Cod sursa (job #2316913) | Cod sursa (job #2774377) | Cod sursa (job #777904) | Cod sursa (job #583395) | Cod sursa (job #1886105)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <stdio.h>
#include <ctype.h>
#define nrmax 100001
using namespace std;
class InParser {
private:
FILE *fin;
char *buff;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
public:
InParser(const char* nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
InParser& operator >> (int &n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
InParser& operator >> (long long &n) {
char c;
n = 0;
while (!isdigit(c = read_ch()) && c != '-');
long long sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
};
InParser f("ctc.in");
ofstream g("ctc.out");
bool used[nrmax];
int st[nrmax];
int n , m , x, y , k , nr;
vector < int > G[nrmax];
vector < int > T[nrmax];
vector < int > ::iterator j;
vector < int > sol[nrmax];
void dfs ( int i )
{
used[i] = 1;
for (vector < int > ::iterator j = G[i].begin(); j != G[i].end(); j++)
{
if ( !used[ (*j) ] )
dfs( (*j) );
}
st[++k] = i;
}
void dfsT ( int i )
{
sol[nr].push_back(i);
used[i] = 1;
for (vector < int > ::iterator j = T[i].begin() ; j != T[i].end(); j++ )
{
if ( !used [ (*j) ] )
dfsT ( (*j) ) ;
}
}
int main()
{
f >> n >> m;
for ( ; m-- ; )
{
f >> x >> y;
G[x].push_back(y);
T[y].push_back(x);
}
for ( int i = 1; i <= n ; i++ )
{
if ( !used[i] ) dfs(i);
}
memset(used,false,sizeof used);
for ( int i = k ; i >= 1; i-- )
{
if ( !used[ st[i] ] )
{
nr++;
dfsT(st[i]);
}
}
g << nr << "\n" ;
for ( int i = 1; i <= nr; i++ )
{
for ( vector < int > ::iterator j = sol[i].begin(); j != sol[i].end(); j++ )
g << (*j) << " " ;
g << "\n" ;
}
return 0;
}