Pagini recente » Cod sursa (job #1142366) | Cod sursa (job #434901) | Cod sursa (job #2903762) | Cod sursa (job #2200737) | Cod sursa (job #2167175)
#include<iostream>
#include<fstream>
#include<vector>
#define N_MAX 100000
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector< int > mat[N_MAX];
vector< int > rev_mat[N_MAX];
vector< int > stk;
vector< vector<int> > sol;
bool viz[N_MAX];
bool viz2[N_MAX];
int n,m;
int strong_c;
void dfs(int node)
{
viz[node] = true;
for(int i=0;i<mat[node].size();i++)
{
if(viz[ mat[node][i] ] == false) dfs(mat[node][i]);
}
stk.push_back(node);
}
void dfs2(int node)
{
viz2[node] = true;
sol[strong_c-1].push_back(node+1);
for(int i=0;i<rev_mat[node].size();i++)
{
if(viz2[ rev_mat[node][i] ] == false) dfs2(rev_mat[node][i]);
}
}
void kosaraju()
{
for(int i=0;i<n;i++)
{
if(viz[i] == false) dfs(i);
}
while(stk.size()>0)
{
int x = stk[stk.size()-1];
stk.pop_back();
if(viz2[x] == false)
{
strong_c++;
vector<int> z;
sol.push_back(z);
dfs2(x);
}
}
}
int main()
{
strong_c = 0;
fin>>n>>m;
int k1,k2;
for(int i=0;i<m;i++)
{
fin>>k1>>k2;
mat[k1-1].push_back(k2-1);
rev_mat[k2-1].push_back(k1-1);
}
kosaraju();
fout<<strong_c<<"\n";
for(int i=0;i<sol.size();i++)
{
for(int j=0;j<sol[i].size();j++)
{
fout<<sol[i][j]<<" ";
}
fout<<"\n";
}
}