Pagini recente » Cod sursa (job #2769928) | Cod sursa (job #2750684) | Cod sursa (job #2854934) | Cod sursa (job #366700) | Cod sursa (job #629791)
Cod sursa(job #629791)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int MAXN = 100002;
int N , M , x , y , indecs;
vector< vector<int> > C;
vector<int> G[MAXN] , lowlink , idx , con;
vector<bool> in_stack;
stack<int> S;
void read_data()
{ fin>>N>>M;
for(;M;M--)
fin>>x>>y , G[x].push_back(y);
idx.resize(N+1), lowlink.resize(N+1), in_stack.resize(N+1);
idx.assign(N+1, -1), in_stack.assign(N+1, 0);
}
void tarjan(const int node)
{
lowlink[node] = idx[node] = indecs;
indecs++;
S.push(node) , in_stack[node] = 1;
for(vector<int>::const_iterator it=G[node].begin();it!=G[node].end();++it)
if(idx[*it]==-1)
tarjan(*it) , lowlink[node] = min(lowlink[node],lowlink[*it]);
else
if (in_stack[*it])
lowlink[node] = min(lowlink[node],lowlink[*it]);
if(idx[node]==lowlink[node])
{
int n;
con.clear();
do
{
con.push_back( n = S.top());
S.pop() , in_stack[node] = 0;
} while(n!=node);
C.push_back(con);
}
}
int main()
{
read_data();
for(int i=1;i<=N;++i)
if(idx[i]==-1) tarjan(i);
fout<<C.size()<<'\n';
for(int i=0;i<(int)C.size();++i)
{
for(int j=0;j<(int)C[i].size();++j)
fout<<C[i][j]<<' ';
fout<<'\n';
}
return 0;
}