Pagini recente » Cod sursa (job #1262776) | Cod sursa (job #3166541) | Cod sursa (job #2397170) | Cod sursa (job #2037912) | Cod sursa (job #2926063)
#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int maxn = 100005;
vector <int> v[maxn];
stack <int> stk;
int id[maxn];
int lowlink[maxn];
bitset <maxn> pestiva;
vector <int> ctc[maxn]; /// ctc[i] = componenta tare conexa cu lowlinkul i
int n;
int currlow = 0;
int currctc = 0;
void dfs(int nod)
{
//cerr << "Intra in nodul " << nod << "\n";
stk.push(nod); /// pun nodul in stiva, initializez id si lowlink
id[nod] = ++currlow;
lowlink[nod] = currlow;
pestiva[nod] = 1;
//cerr << "La pasul " << nod << ":\n";
/*for(int i = 1; i <= n; i++)
cerr << id[i] << " ";
cerr << "\n";
for(int i = 1; i <= n; i++)
cerr << lowlink[i] << " ";
cerr << "\n\n";
*/
for(auto it : v[nod])
{
if(id[it] == 0) /// vecin nevizitat
{
dfs(it);
lowlink[nod] = min(lowlink[nod], lowlink[it]);
}
else if(pestiva[it])
lowlink[nod] = min(lowlink[nod], lowlink[it]);
}
/*
int mn = (1 << 30);
for(auto it : v[nod]) /// iau lowlinkul minim din vecini
mn = min(mn, lowlink[it]);
cerr << "Minim: " << mn << "\n";
while(id[stk.top()] != mn)
{
cerr << "Stiva " << stk.top() << "\n";
lowlink[stk.top()] = mn;
pestiva[stk.top()] = 0;
stk.pop();
}
*/
if(lowlink[nod] == id[nod]) /// daca e inceput de ctc
{
currctc++;
while(stk.top() != nod)
{
ctc[currctc].push_back(stk.top());
pestiva[stk.top()] = 0;
stk.pop();
}
ctc[currctc].push_back(nod);
pestiva[nod] = 0;
stk.pop();
}
}
int main()
{
int m;
in >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y;
in >> x >> y;
v[x].push_back(y);
}
for(int i = 1; i <= n; i++)
if(!id[i])
dfs(i);
out << currctc << "\n";
for(int i = 1; i <= currctc; i++, out << "\n")
for(auto it : ctc[i])
out << it << " ";
return 0;
}