Pagini recente » Cod sursa (job #1556601) | Cod sursa (job #1732325) | Cod sursa (job #1877085) | Cod sursa (job #2641107) | Cod sursa (job #741231)
Cod sursa(job #741231)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int MAX = 100050;
int n, index, idx[MAX], lowlink[MAX], in_stack[MAX];
vector<int> v[MAX], con; vector< vector < int > > sol;
stack<int> stk;
void citire()
{
ifstream in("ctc.in");
int m, a, b;
in>>n>>m;
while(m--)
{
in>>a>>b;
v[a].push_back(b);
}
in.close();
}
void init()
{
for(int i = 1; i <= n; i++)
{
idx[i] = lowlink[i] = -1;
in_stack[i] = 0;
}
}
void tarjan(int n)
{
idx[n] = lowlink[n] = index; index++;
stk.push(n); in_stack[n] = 1;
for(vector<int>::iterator it = v[n].begin(); it != v[n].end(); it++)
{
if(idx[*it] == -1)
{
tarjan(*it);
lowlink[n] = min(lowlink[n], lowlink[*it]);
}
else if(in_stack[*it])
lowlink[n] = min(lowlink[n], lowlink[*it]);
}
if(idx[n] == lowlink[n])
{
con.clear();
int nod;
do
{
con.push_back(nod = stk.top());
stk.pop(); in_stack[nod] = 0;
}while(nod != n);
sol.push_back(con);
}
}
void solve()
{
for(int i = 1; i <= n; i++)
if(idx[i] == -1)
tarjan(i);
}
void afisare()
{
ofstream out("ctc.out");
out<<sol.size()<<'\n';
for(size_t i = 0; i < sol.size(); i++)
{
for(size_t j = 0; j < sol[i].size(); j++)
out<<sol[i][j]<<" ";
out<<'\n';
}
out.close();
}
int main()
{
citire();
init();
solve();
afisare();
return 0;
}