Pagini recente » Cod sursa (job #2778213) | Cod sursa (job #149284) | Cod sursa (job #3000197) | Cod sursa (job #1499104) | Cod sursa (job #1914708)
#include <bits/stdc++.h>
#define buff_size 3666013
char buff[buff_size];
int pos=0;
char outBuff[buff_size];
int outPtr;
FILE*f=freopen("ctc.in","r",stdin);
FILE*g=freopen("ctc.out","w",stdout);
using namespace std;
int n,m;
bitset<100001> visited;
int ST[100001],k=0;
vector <int> G[100001];
vector <int> G_reversed[100001];
int components_number=0;
vector<int> components[100001];
inline void read(int &nr)
{
while(!isdigit(buff[pos])) if(++pos == buff_size) fread(buff, 1,buff_size, stdin), pos = 0;
nr = 0;
while(isdigit(buff[pos]))
{
nr = (nr<<1)+(nr<<3)+ buff[pos] - 48;
if(++pos == buff_size) fread(buff, 1, buff_size, stdin), pos = 0;
}
}
inline void putChar(const char &C)
{
outBuff[outPtr++] = C;
if (outPtr == buff_size) {
fwrite(outBuff, 1, buff_size, stdout);
outPtr = 0;
}
}
inline void write(int X)
{
static char digs[10];
int n = 0, q;
do {
q = X / 10;
digs[n++] = X - (q << 1) - (q << 3) + 48;
X = q;
} while (X);
while (n--) {
putChar(digs[n]);
}
}
void read_data()
{
int x,y;
read(n);read(m);
for(int i=1;i<=m;i++)
{
read(x);read(y);
G[x].push_back(y);
G_reversed[y].push_back(x);
}
}
void DFS(int node)
{
visited[node]=1;
for(size_t i=0;i<G[node].size();i++)
{
int next_node=G[node][i];
if(visited[next_node]==0) DFS(next_node);
}
ST[++k]=node;
}
void DFS2(int node)
{
visited[node]=0;
for(size_t i=0;i<G_reversed[node].size();i++)
{
int next_node=G_reversed[node][i];
if(visited[next_node]==1) DFS2(next_node);
}
components[components_number].push_back(node);
}
void kosaraju()
{
for(int i=1;i<=n;i++) if(visited[i]==0) DFS(i);
for(int i=k;i>=1; i--) if(visited[ST[i]]==1) components_number++,DFS2(ST[i]);
}
void write_result()
{
write(components_number);putChar('\n');
for(int i=1;i<=components_number;i++)
{
for(int j=0;j<components[i].size();j++) write(components[i][j]),putChar(' ');
putChar('\n');
}
fwrite(outBuff, 1, buff_size, stdout);
}
int main()
{
read_data();
kosaraju();
write_result();
}